1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| #include<cstdio>
#include<algorithm>
#include<ctype.h>
#include<string.h>
#include<math.h>
using namespace std;
#define ll long long
const int N = 50005, M = 1<<16, P = 1000000007;
int cnt, n, m, l, prime[N], f[M], g[M];
bool p[N];
inline int Pow(ll x, int y=P-2){
int ans=1;
for(; y; y>>=1, x=x*x%P) if(y&1) ans=ans*x%P;
return ans;
}
inline void FWT(int *f, int g){
for(int i=1; i<l; i<<=1) for(int j=0; j<l; j+=i<<1)
for(int k=j; k<j+i; ++k){
int x=f[k], y=f[k+i];
f[k]=(x+y)%P, f[k+i]=(P+x-y)%P;
}
if(g==-1) for(int i=0, I=Pow(l); i<l; ++i) f[i]=(ll)f[i]*I%P;
}
inline void mul(int *f, int *g){ for(int i=0; i<l; ++i) f[i]=(ll)f[i]*g[i]%P;}
int main() {
for(int i=2; i<=50000; ++i){
if(!p[i]) prime[++cnt]=i;
for(int j=1; j<=cnt && i*prime[j]<=50000; ++j){
p[i*prime[j]]=1;
if(i%prime[j]==0) break;
}
}
while(~scanf("%d%d", &n, &m)){
memset(f, 0, sizeof f);
for(int i=1; i<=cnt && prime[i]<=m; ++i) f[prime[i]]=1;
for(l=1; l<=m; l<<=1);
FWT(f, 1);
memcpy(g, f, l<<2);
for(--n; n; n>>=1, mul(f, f)) if(n&1) mul(g, f);
FWT(g, -1);
printf("%d\n", g[0]);
}
return 0;
}
|