NonZero PrefSuf Sums#12971

NonZero PrefSuf Sums

2 seconds
512 megabytes
Very hard

Prince Charming wanted to give you a long, tedious legend full of pomp and flair. But Shrek won’t allow this! He gives you a completely formal and short statement instead.

Count the number of arrays [a_1, a_2, \dots, a_n] of integers that satisfy the following conditions:

  1. |a_i| \leq m for all 1 \leq i \leq n.

  2. There exists a permutation [b_1, b_2, \dots, b_n] of elements of , such that the following holds: b_1 + b_2 + \dots + b_k \neq 0 for all 1 \leq k \leq n.

  3. b_k + b_{k+1} + \dots + b_n \neq 0 for all 1 \leq k \leq n.

Output the answer modulo , where is a big prime number.

Input

The only line of the input contains three integers , , .

2 \leq n \leq 100,

1 \leq m \leq 100,

10^8 < p < 10^9, is prime.

Output

Output a single integer — the answer modulo .

Examples

Example

Loading
Loading

Example 1

Loading
Loading

Note

In the first test case, there are possible arrays: , , , , , , , , . Only arrays and satisfy the condition from the problem.