oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

pokebattle Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

pokebattle.html

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:
  1. Ember
  2. Ember, Growl
  3. Ember, (switch to Rattata), Tackle
  4. Ember, (switch to Rattata), Tail Whip
  5. Ember, (switch to Rattata), Quick Attack
  6. Growl, Ember
  7. (switch to Rattata), Tackle, (switch to Charmander), Ember
  8. (switch to Rattata), Tail Whip, (switch to Charmander), Ember
  9. (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.

Tags

Ad Hoc, Brute Force

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
1100201s32MBAverage
2011s32MBAverage

Judge Compile Command

g++-8 ans.cpp -o pokebattle -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.