和https://www.cnblogs.com/xzz_233/p/10060753.html一样，都是多项式快速幂，还比那个题水。

设\(a[i]\)表示\([1,m]\)中$ \mod p\(余\)i\(的数的个数，\)f[i][j]\(表示用\)i\(个\)[1,m]\(中的数凑出\)j$的方案数

那么转移方程是\(f[i][j]=\sum_{k=0}^{p-1}f[i-1][(j-k)\mod m]\times a[k]\)

直接多项式快速幂即可

但是还有2条件，至少选一个质数，其实就是全都能选的减去不选质数的方案数

另外，这个模数要用，贼简单，懒得写了，咕咕咕

#include
    
     #define il inline#define vd void#define mod 20170408#define M 4491typedef long long ll;il int gi(){    int x=0,f=1;    char ch=getchar();    while(!isdigit(ch)){        if(ch=='-')f=-1;        ch=getchar();    }    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();    return x*f;}typedef std::complex
     
       cp;int n,m,p,ANS;int rev[257],N,lg;cp FA[257],FB[257],GA[257],GB[257],omg[257],inv[257];struct naive{    int t[100];    il int& operator [](int x){return t[x];}};il vd fft(cp*A,int n,cp*omg){    for(int i=0;i
      
       i)std::swap(A[rev[i]],A[i]);    for(int o=1;o
       
        <<=1)        for(cp*p=A;p!=A+n;p+=o<<1)            for(int i=0;i
        
         >1]>>1)|((i&1)<
         
          >=1; } ANS+=ans[0]; static int pri[20000000],pr=0; static bool yes[20000001]; for(int i=0;i
          
           >=1; } ANS-=ans[0]; printf("%d\n",(ANS+mod)%mod); return 0;}