思路：
\(令f_{ij}为选i个数总和取模p为j\)
\(\therefore f_{ij}=\sum_{k=0}^{p-1}f_{mid\ k}f_{(i-mid)\ (p-k)}+\sum_{k=0}^{p-1}f_{mid\ k}f_{(i-mid)\ (2p-k)}\)
\(刚好是卷积的形式\)
\(我们发现mid取\lfloor\frac{l+r}{2}\rfloor,把卷积拆成f_{mid}*f_{mid}*f_1，用类似快速幂的方式实现\)
\(还有结果为所有解减去没有质数的解\)
\(时间复杂度O(p^2log_2n)\)
\(\mathfrak{Talk\ is\ cheap,show\ you\ the\ code.}\)
#include<cstdio>
#include<cmath>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
# define read read1<int>()
# define Type template<typename T>
Type inline T read1(){
T n=0;
char k;
bool fl=0;
do (k=getchar())=='-'&&(fl=1);while('9'<k||k<'0');
while(47<k&&k<58)n=(n<<3)+(n<<1)+(k^48),k=getchar();
return fl?-n:n;
}
# define f(i,l,r) for(int i=(l);i<=(r);++i)
# define fre(k) freopen(k".in","r",stdin);freopen(k".ans","w",stdout)
# define ll long long
# define mod 20170408
ll f[101],n,m,tem[201],h[101];
int p;
void dfs(int n){
if(n==1){memcpy(f,h,sizeof(f));return;}
dfs(n>>1);
for(int i=0;i<p*2;++i)tem[i]=0;
for(int i=0;i<p;++i)for(int j=0;j<p;++j)
tem[i+j]=(tem[i+j]+f[i]*f[j])%mod;
for(int i=0;i<p;++i)f[i]=tem[i]+tem[i+p];
if(n&1){
for(int i=0;i<p*2;++i)tem[i]=0;
for(int i=0;i<p;++i)for(int j=0;j<p;++j)
tem[i+j]=(tem[i+j]+f[i]*h[j])%mod;
for(int i=0;i<p;++i)f[i]=tem[i]+tem[i+p];
}
}
bool vis[20000001];
int main(){
n=read,m=read,p=read;
for(int i=1;i<=m;++i)++h[i%p];
dfs(n);
ll tem=f[0];
for(int i=2;i<=m;++i){
if(!vis[i])--h[i%p];
for(ll j=(ll)i*i;j<=m;j+=i)
vis[j]=1;
}
dfs(n);
printf("%lld",(tem-f[0]+mod)%mod);
return 0;
}