It might be failing because of integer overflow. If they're asking you to compute the result modulo 10056, it means that the result will probably be huge (even bigger than the biggest long long integer).

You must use this fact: , assuming that is the classic % operator in C/C++. This way you won't exceed integer's capacity.

Cool problem! You need to consider combinations, I think that's why your idea fails. Let me break down case n = 3, hopefully you'll see the recurrence:

• Everyone comes in 1st: clearly order doesn't matter, so just add 1 to your answer.

• Two guys come in 1st: could be (1, 2), (1, 3), or (2, 3) -that is combinations of 3 elements picked 2 at a time. The other guy can only be 3, 2, or 1 correspondingly, so add (3 * 1) to the answer.

• 1 guy wins: must be 1, 2, or 3 (comb. of 3 elements picked 1 at a time)! What happens to the remaining positions? They could have tied, or one guy beat the other... But hey, isn't that case n = 2 (which you described in your example)! So, add to the solution (3 * 3).

Hope that helped!

Simply put DP: let P[n] denote the number of ways n horses could finish the race; all operations will be done mod m.

Out of n horses, any 1 ≤ k ≤ n could've taken first place; the number of ways to choose k horses is . The remaining n - k horses finished in 2nd..x-th place, which is the same as a result of a race with n - k horses. Therefore, we get a recurrence relation

with $P[0]=1$.