单点时限: 1.0 sec
内存限制: 512 MB
这是一个无聊的数学题。
非形式化地说：从 0,1,…,2n−1 中选出若干个数，使得这些数的异或和为 k。求有多少种方案？
形式化地说：现给出 n,p,k，输出 0,1,…,2n−1 有多少个非空子集异或和恰好为 k。输出结果模 p 的值。
一行三个整数 n, k, p (1≤n≤1018, 0≤k≤min(2n−1,1018), 2≤p≤109, p 是质数)。
2 3 998244353
4
样例解释：k=3，有以下四个方案：1,2, 3, 0,3, 0,1,2。
在数字逻辑中，异或是对两个运算元的一种逻辑分析类型，符号为 XOR 或 ⊕。与一般的逻辑或 OR 不同，当两两数值相同为否，而数值不同时为真。对于任意两个数的异或：先写出这两个数的二进制表示，然后对于每一位进行异或。在 C 语言中写作 a ^ b。
a ^ b