Let S = {1, 2, 3, ..., N}.
For a given positive integer K, the function f : S --> S is called "pretty" if, for every X in S, it holds that
f ( f ( f ( ... f ( X ) ... ) ) ) = X, where f is repeated exactly K times.

How many pretty functions are there, modulo M?

Input

Three natural numbers N, K and M. It holds that 1 <= K <= N <= 30 000 and M <= 10^9.

Output

Number of pretty functions modulo M.

Example

Input:
2 1
1000

Output:
1

Input:
3 2
1000

Output:
4

Explanation of the example input 2: there are four pretty functions, namely:
a) f(1) = 1, f(2) = 2, f(3) = 3;
b) f(1) = 2, f(2) = 1, f(3) = 3;
c) f(1) = 3, f(2) = 2, f(3) = 1;
d) f(1) = 1, f(2) = 3, f(3) = 2.