405220: GYM101848 D XOR
Memory Limit：512 MB
Time Limit：1 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
D. XORtime limit per test1 secondmemory limit per test512 megabytesinputstandard inputoutputstandard 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.
InputThree space-separated integers n, k, p. (1 ≤ n ≤ 1018, 0 ≤ k ≤ min(2n - 1, 1018), 2 ≤ p ≤ 109, p is prime.)
OutputOutput an integer denoting the answer.
ExampleInput2 3 998244353Output
4Note
When n = 2 and k = 3, we have the following 4 possible subsets: {1, 2}, {3}, {0, 3}, {0, 1, 2}.