D. XOR
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

Given n, k, p, Count the number of non-empty subsets of {0, 1, ..., 2n - 1} such that the xor-sum of the subset is exactly k. Output the answer modulo p.

Input

Three space-separated integers n, k, p. (1 ≤ n ≤ 1018, 0 ≤ k ≤ min(2n - 1, 1018), 2 ≤ p ≤ 109, p is prime.)

Output

Output an integer denoting the answer.

Example
Input
2 3 998244353
Output
4
Note

When n = 2 and k = 3, we have the following 4 possible subsets: {1, 2}, {3}, {0, 3}, {0, 1, 2}.