1374 - Just Another Game

Time Limit: 5s Memory Limit: 128MB

Submissions: 153 Solved: 28
HH and LL always play games together, however, LL won every time~~.That make HH very unhappy, so this time HH is designing a new game for beating LL. Here comes the rule of the game: 1)there are exactly K piles of stones on the big table. 2)the two players play in turn. 3)on each round, the player choose a pile with fewest number of stones, and remove some stones from that pile(one to the whole pile). 4)the one who take the last stone win. Now HH has N stones in hand. In order to play the game, he is going to distribute all the N stones into K piles. For the sake of fairness, he lets LL play first. As is known to all, HH and LL are both clever boys. So they play optimally in the game. Here comes the question, HH wants to know how many different ways he can distribute the stones so that he can win the game. Assumed that the answer is X, tell him the number equal to X modulo M. NOTE: two way of distributions are considered the same if they are exactly the same after sorting in ascendant order. (i.e. 1, 3, 4, 4 and 4, 1, 3, 4 are the same, while 1, 2, 2 and 1, 2 are not).
The input contains several test cases, each line representing one case. Each line contains three integer N, K, M (1 <= N <= 200, 1 <= K <= N, 1 <= M <= 1000,000,000)
For each case output a line containing the answer described above.
Sample Input
2 1 100
6 2 100
Sample Output
For the second case, the only way of distribution is 1, 5.
Hust Monthly 10.06.13/Xiaobin YANG