See problem SPY for more background information.

Blue Mary extremely likes making PPTs. She has already made 2L PPTs. Now the only problem before finishing is to set the background pictures for each PPT. She has an odd number (denoted by N) of background pictures ranging from 0 to N-1 inclusive. Each PPT needs exactly one background picture. Different PPTs can use same background pictures. Obviously, there are N^2L combinations.

For each combination, Blue Mary defines its weight as the sum of the IDs of the first L PPTs minus the sum of the IDs of the last L PPTs. Now Blue Mary wants to calculate the number of combinations with a positive weight. (Blue Mary is such a weird girl that she always does some meaningless calculations.) She asks you for help.

Since this number can be quite large, Blue Mary only needs the number modulo a prime P.

Input

Several test cases, the number of which is less than 3333. Each test case consists of a single line with three space-separated integers N (1 <= N <= 3333), L (1 <= L <= 3333) and P (10⁸ <= P <= 10⁹). Input terminates by EOF.

Input data is generated with almost log-uniform random distribution.

Output

For each test case, output the required value in a single line.

Example

Input:
1 1 100000007
3 2 999999937

Output:
0
31