#include<bits/stdc++.h> #define ll long long using namespace std; const int maxn=5e4+100; const int mod=1e9+7; const int MOD=1e9+7; const int inv2=5e8+4; int a[1<<17],b[1<<17],N; int n,m; bool vis[maxn]; int prime[maxn]; int tot=0; void get_prime() // prime=0;else 1; { vis[1]=1; for(int i=2;i<maxn;i++) { if(!vis[i]) prime[tot++]=i; for(int j=0;j<tot && i*prime[j]<maxn;j++) { vis[i*prime[j]]=1; if(i%prime[j]==0) break; } } //for(int i=0;i<=40;i++) cout<<prime[i]<<endl; } void FWT(int *P,int opt) { for(int i=2;i<=N;i<<=1) for(int p=i>>1,j=0;j<N;j+=i) for(int k=j;k<j+p;++k) { int x=P[k],y=P[k+p]; P[k]=(x+y)%MOD;P[k+p]=(x-y+MOD)%MOD; if(opt==-1)P[k]=1ll*P[k]*inv2%MOD,P[k+p]=1ll*P[k+p]*inv2%MOD; } } void fpow(int *a,int *b,int p) { FWT(a,1); FWT(b,1); while(p) { if(p&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; p>>=1; } FWT(b,-1); } int main() { get_prime(); while(scanf("%d %d",&n,&m)!=EOF) { N=1; while(N<=m) N=N<<1; memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); for(int i=1;i<=m;i++) if(!vis[i]) a[i]=b[i]=1; fpow(a,b,n-1); printf("%d\n",b[0]); } return 0; }