1374 - Just Another Game

Time Limit : 5 Second

Memory Limit : 128 MB

Submission: 153

Solved: 28

Description
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).
Input
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)
Output
For each case output a line containing the answer described above.
sample input
2 1 100
6 2 100
sample output
0
1
hint
For the second case, the only way of distribution is 1, 5.
source
Hust Monthly 10.06.13/Xiaobin YANG
© 2015 HUST ACMICPC TEAM. All Right Reserved.