Description：

求 $n$ 堆石子每堆初始数量是不超过 $m$ 的质数，按照最优策略玩游戏，那么后手能获胜的局面有多少种。

$1\leqslant n\leqslant 10^9,1\leqslant m\leqslant50000$

Solution：

根据尼姆游戏我们知道后手能赢当且仅当所有石子异或和为 $0$ ，如果他让求的是所有石子个数和为一个给定的数，那显然是用生成函数 $FFT$ 做快速幂，但是这个是异或和，那就还像这个一样给每个合法的质数位置加一，然后求快速幂，只不过这个用 $FWT$ 求就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXM 100010

bool isprime[MAXM];

int prime[MAXM],tot = 0;

typedef long long ll;

#define MOD 1000000007

ll a[MAXM],res[MAXM];

#define INV2 500000004

void FWT(ll f[],int l,int type)

{

	for(int i = 2;i <= l;i = i << 1)

	{

		for(int j = 0;j < l;j += i)

		{

			for(int k = j;k < j + i / 2;++k)

			{

				ll u = f[k],t = f[k + i / 2];

				f[k] = (u + t) % MOD;

				f[k + i / 2] = (u - t + MOD) % MOD;

				if(type == -1)

				{

					f[k] = f[k] * INV2 % MOD;

					f[k + i / 2] = f[k + i / 2] * INV2 % MOD;

				}

			}

		}

	}

	return;

}

void KSM(int l)

{

	memset(res,0,sizeof(res));

	res[0] = 1;

	FWT(a,l,1);FWT(res,l,1);

	while(n > 0)

	{

		if(n & 1)

		{

			for(int i = 0;i < l;++i)

			{

				res[i] = res[i] * a[i] % MOD;

			}

		}

		for(int i = 0;i < l;++i)a[i] = a[i] * a[i] % MOD;

		n = n >> 1;

	}

	FWT(res,l,-1);

	return;

}

int main()

{

	for(int i = 2;i < MAXM;++i)isprime[i] = true;

	for(int i = 2;i < MAXM;++i)

	{

		if(isprime[i])prime[++tot] = i;

		for(int j = 1;j <= tot && i * prime[j] < MAXM;++j)

		{

			isprime[i * prime[j]] = false;

			if(i % prime[j] == 0)break;

		}

	}

	while(scanf("%d%d",&n,&m) != EOF)

	{

		memset(a,0,sizeof(a));

		for(int i = 2;i <= m;++i)

		{

			if(isprime[i])a[i] = 1;

		}

		int l = 0,len = 1;

		for(;len <= m;len = len << 1,++l);

		KSM(len);

		printf("%lld\n",res[0]);

	}

	return 0;

}