Description
Claris和NanoApe在玩石子游戏，他们有n堆石子，规则如下：
1. Claris和NanoApe两个人轮流拿石子，Claris先拿。
2. 每次只能从一堆中取若干个，可将一堆全取走，但不可不取，拿到最后1颗石子的人获胜。
不同的初始局面，决定了最终的获胜者，有些局面下先拿的Claris会赢，其余的局面Claris会负。
Claris很好奇，如果这n堆石子满足每堆石子的初始数量是不超过m的质数，而且他们都会按照最优策略玩游戏，那么NanoApe能获胜的局面有多少种。
由于答案可能很大，你只需要给出答案对10^9+7取模的值。
Input
输入文件包含多组数据，以EOF为结尾。
对于每组数据：
共一行两个正整数n和m。
每组数据有1<=n<=10^9, 2<=m<=50000。
不超过80组数据。
Output
Sample Input
3 7
4 13
4 13
Sample Output
6
120
120
正解：$FWT$。
背了一下板子。。
这个东西可以用来求$C=Aotimes B$，其中$C_{i}=sum_{j otimes k=i}a_{j}b_{k}$。
然后大概就是一些逻辑运算符，比如说与，或，异或什么的。。
写了个板子在下面，上面$3$种情况都列举了。不过为什么是对的。。
1 //It is made by wfj_2048~ 2 #include <algorithm> 3 #include <iostream> 4 #include <cstring> 5 #include <cstdlib> 6 #include <cstdio> 7 #include <vector> 8 #include <cmath> 9 #include <queue> 10 #include <stack> 11 #include <map> 12 #include <set> 13 #define rhl (1000000007) 14 #define inf (1<<30) 15 #define il inline 16 #define RG register 17 #define ll long long 18 #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout) 19 20 using namespace std; 21 22 int f[150010],a[150010],vis[100010],prime[100010],N,n,m,cnt,inv; 23 24 il int gi(){ 25 RG int x=0,q=1; RG char ch=getchar(); 26 while ((ch<'0' || ch>'9') && ch!='-') ch=getchar(); 27 if (ch=='-') q=-1,ch=getchar(); 28 while (ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar(); 29 return q*x; 30 } 31 32 il ll qpow(RG ll a,RG ll b){ 33 RG ll ans=1; 34 while (b){ 35 if (b&1) ans=ans*a%rhl; 36 a=a*a%rhl,b>>=1; 37 } 38 return ans; 39 } 40 41 il void sieve(){ 42 for (RG int i=2;i<=50000;++i){ 43 if (!vis[i]) prime[++cnt]=i; 44 for (RG int j=1,k;j<=cnt;++j){ 45 k=i*prime[j]; if (k>50000) break; 46 vis[k]=1; if (i%prime[j]==0) break; 47 } 48 } 49 return; 50 } 51 52 il void fwt(int *a,RG int n){ 53 for (RG int i=1;i<n;i<<=1) 54 for (RG int j=0;j<n;j+=(i<<1)) 55 for (RG int k=0,x,y;k<i;++k){ 56 x=a[j+k],y=a[j+k+i]; 57 a[j+k]=x+y; if (a[j+k]>=rhl) a[j+k]-=rhl; 58 a[j+k+i]=x-y; if (a[j+k+i]<0) a[j+k+i]+=rhl; 59 //and:a[j+k]=x+y; 60 //or:a[j+k+i]=x+y; 61 //xor:a[j+k]=x+y,a[j+k+i]=x-y; 62 } 63 return; 64 } 65 66 il void ufwt(int *a,RG int n){ 67 for (RG int i=1;i<n;i<<=1) 68 for (RG int j=0;j<n;j+=(i<<1)) 69 for (RG int k=0,x,y;k<i;++k){ 70 x=a[j+k],y=a[j+k+i]; 71 a[j+k]=(int)((ll)inv*(ll)(x+y)%rhl); 72 a[j+k+i]=(int)((ll)inv*(ll)(x-y+rhl)%rhl); 73 //and:a[j+k]=x-y; 74 //or:a[j+k+i]=y-x; 75 //xor:a[j+k]=(x+y)/2,a[j+k+i]=(x-y)/2; 76 } 77 return; 78 } 79 80 il void work(){ 81 if (n==1){ puts("0"); return; } 82 for (N=1;N<=m;N<<=1); memset(a,0,sizeof(a)); 83 for (RG int i=1;i<=cnt && prime[i]<=m;++i) a[prime[i]]=1; 84 memset(f,0,sizeof(f)),f[0]=1,fwt(f,N),fwt(a,N); 85 while (n){ 86 if (n&1){ 87 for (RG int i=0;i<N;++i) f[i]=(int)((ll)f[i]*(ll)a[i]%rhl); 88 } 89 for (RG int i=0;i<N;++i) a[i]=(int)((ll)a[i]*(ll)a[i]%rhl); 90 n>>=1; 91 } 92 ufwt(f,N); printf("%d ",f[0]); return; 93 } 94 95 int main(){ 96 File("hardnim"); 97 sieve(),inv=qpow(2,rhl-2); 98 while (scanf("%d%d",&n,&m)!=EOF) work(); 99 return 0; 100 }