Description
Claris 和 NanoApe 在玩石子游戏，他们有 \(n\) 堆石子，规则如下：
- Claris 和 NanoApe 两个人轮流拿石子，Claris 先拿。
- 每次只能从一堆中取若干个，可将一堆全取走，但不可不取，拿到最后 \(1\) 颗石子的人获胜。
不同的初始局面，决定了最终的获胜者，有些局面下先拿的 Claris 会赢，其余的局面 Claris 会负。
Claris 很好奇，如果这 \(n\) 堆石子满足每堆石子的初始数量是不超过 \(m\) 的质数，而且他们都会按照最优策略玩游戏，那么 NanoApe 能获胜的局面有多少种。
由于答案可能很大，你只需要给出答案对 \(10^9+7\) 取模的值。
Input
输入包含多组数据，每组数据一行两个正整数 \(n\) 和 \(m\)。
Output
每行一个整数表示答案。
Sample Input
3 74 13
Sample Output
6120
HINT
\(1\le n\le 10^9, 2\le m\le 50000\)
不超过 \(80\) 组数据。
Solution
NIM 游戏先手必胜的条件是每堆石子数的异或和为 \(0\)。
相当于将一个只有质数次项的系数是 \(1\)，其他项的系数是 \(0\) 的 \(m\) 次多项式 \(fwt\) 异或卷积 \(n\) 次，最后输出常数项。
Code
#includeconst int mod = 1000000007, inv = 500000004;int n, m, nn, p[5135], np[50001], tot, a[65540], b[65540];void euler(int n) { for (int i = 2; i <= n; ++i) { if (!np[i]) p[++tot] = i; for (int j = 1; j <= tot && i * p[j] <= n; ++j) { np[i * p[j]] = 1; if (i % p[j] == 0) break; } }}void fwt(int *a, int f) { for (int i = 1; i < n; i <<= 1) for (int j = 0, r = i << 1; j < n; j += r) for (int k = 0; k < i; ++k) { int x = a[j + k], y = a[i + j + k]; a[j + k] = 1LL * (x + y) % mod, a[i + j + k] = 1LL * (x + mod - y) % mod; if (f == -1) a[j + k] = 1LL * a[j + k] * inv % mod, a[i + j + k] = 1LL * a[i + j + k] * inv % mod; }}int fastpow(int k) { for (; k; k >>= 1) { if (k & 1) for (int i = 0; i < n; ++i) b[i] = 1LL * b[i] * a[i] % mod; for (int i = 0; i < n; ++i) a[i] = 1LL * a[i] * a[i] % mod; } fwt(b, -1); return b[0];}int main() { euler(50000); while (~scanf("%d%d", &nn, &m)) { for (n = 1; n <= m; n <<= 1) {} for (int i = 0; i < n; ++i) a[i] = 0; for (int i = 1; i <= tot && p[i] <= m; ++i) a[p[i]] = 1; fwt(a, 1); for (int i = 0; i < n; ++i) b[i] = a[i]; printf("%d\n", fastpow(nn - 1)); } return 0;}