SPY3 - Spy Reloaded

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 N2L 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 (108 <= P <= 109). 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

Added by:Fudan University Problem Setters
Date:2023-01-18
Time limit:33s
Source limit:3333B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Based on a Problem from NEERC Western Subregional Contest 20XX

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.