#include<stdio.h>
#define mod 1000000007
typedef long long lld;
int n, m, mx;
lld fac[300000], soin[200000], dap;
lld exp(lld x, lld y){
if(y==0)return 1;
lld im=exp(x,y/2);
im=(im*im)%mod;
if(y%2)im=(im*x)%mod;
return im;
}
lld comb(lld a, lld b){
lld im=fac[a-b]*fac[b]%mod;
return fac[a]*exp(im,mod-2)%mod;
}
int main(){
int i, a;
scanf("%d%d", &n, &m);
for(i=0; i<m; i++){
scanf("%d", &a);
if(mx<a)mx=a;
}
fac[0]=1;
for(i=1; i<300000; i++)fac[i]=fac[i-1]*i%mod;
soin[1]=1;
for(i=2; i<=mx; i++){
for(a=2; a*a<=i; a++){
if(i%a==0)break;
}
if(a*a>i)soin[i]=-1;
else if(i%(a*a)==0)soin[i]=0;
else soin[i]=soin[i/a]*soin[a];
}
for(i=1; i<=mx; i++){
dap+=soin[i]*comb(mx/i+n-1, n);
dap=(dap+mod)%mod;
}
printf("%lld", dap);
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
60 ms |
4992 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
