You are a Pokemon trainer with P Pokemon. Each Pokemon has some moves that deal some damage. Specifically, the ith Pokemon has Mi moves, and the jth of these moves deals Di,j HP damage (1 ≤ i ≤ P, 1 ≤ j ≤ Mi). You are fighting an enemy Missingno (a virus Pokemon) with H HP. This peculiar enemy does not deal damage to your Pokemon for the first K of your moves, and your moves can never miss it too. However, since it's a virus Pokemon, it glitches all your moves such that they can be used only 1 time at most. Furthermore, after K of your Pokemon's moves, if Missingno still has more than 0 HP, it will burst into an outrage and destroy all of your Pokemon.
Naturally, you are interested to know, how many move orderings are there such that Missingno will have 0 or less HP within K turns? The first Pokemon you send out will be the (i = 1)st Pokemon, and you are allowed to switch Pokemon at any point in time.
Input
On the first line are integers
H (1 ≤
H ≤ 1,000,000,000),
P (1 ≤
P ≤ 6) and
K (1 ≤
K ≤
M1+
M2+...+
MP). This is followed by
P lines. The
ith of these lines represents the moveset for the
ith Pokemon. The first integer in the
ith line will be the integer
Mi (1 ≤
Mi ≤ 4), then
Mi integers separated by spaces, the
jth of these integers being the integer
Di,j (0 ≤
Di,j ≤ 60,000,000).
Output
On the first and only line, output the number of move orderings modulo 13,371,337.
Sample Input 1
4 2 2
2 4 0
3 1 0 2
Sample Output 1
9
Explanation for Sample Output 1
We shall assume that the first Pokemon is Charmander with moves Ember and Growl that deal 4 and 0 damage respectively; while the second Pokemon is Rattata with moves Tackle, Tail Whip and Quick Attack that do 1, 0, and 2 damage respectively. The possible move orderings will then be:
- Ember
- Ember, Growl
- Ember, (switch to Rattata), Tackle
- Ember, (switch to Rattata), Tail Whip
- Ember, (switch to Rattata), Quick Attack
- Growl, Ember
- (switch to Rattata), Tackle, (switch to Charmander), Ember
- (switch to Rattata), Tail Whip, (switch to Charmander), Ember
- (switch to Rattata), Quick Attack, (switch to Charmander), Ember
Note that two move orderings with different switching points but same order of moves will be considered the same. For instance, the move ordering {Scratch, (switch to Rattata), Tackle} is the same as {Scratch, (switch to Rattata), (switch to Charmander), (switch to Rattata), Tackle}. Note also that Missingno is a virus Pokemon that defies all logic and hence you can still damage it after its HP reaches 0 as long as you have not used up
K moves yet.