//f[i][j][1/0]表示长为i,sum mod p=j,是否已经选了质数的方案数#include<cstdio>using namespace std;const int mod=20170408;const int N=1e6+1;int tot,prime[N/3];bool check[N];int n,m,f[2][N][2];int p;void pre(){    n=1e6;check[0]=check[1]=1;    for(int i=2;i<=n;i++){        if(!check[i]) prime[++tot]=i;        for(int j=1;j<=tot&&i*prime[j]<=n;j++){            check[i*prime[j]]=1;            if(!(i%prime[j])) break;        }     }}int main(){    freopen("count.in","r",stdin);    freopen("count.out","w",stdout);    pre();    scanf("%d%d%d",&n,&m,&p);    for(int i=1;i<=m;i++) f[1][i%p][!check[i]]++;    for(int i=1,val;i<n;i++){        for(int j=0;j<p;j++){            for(int k=1;k<=m;k++){                val=(j+k)%p;                if(!check[k]){                    f[i+1&1][val][1]=(f[i+1&1][val][1]+f[i&1][j][0]+f[i&1][j][1])%mod;                }                else{                    f[i+1&1][val][0]=(f[i+1&1][val][0]+f[i&1][j][0])%mod,                    f[i+1&1][val][1]=(f[i+1&1][val][1]+f[i&1][j][1])%mod;                }            }        }        for(int j=0;j<p;j++){            f[i&1][j][0]=0;            f[i&1][j][1]=0;        }    }    printf("%d",f[n&1][0][1]);    return 0;}

#include<cstdio>using namespace std;const int mod=20170408;const int N=1e6+1;int tot,prime[N/3];bool check[N];int n,m,p;int f[2][N];int g[2][N];int sz[N];void pre(){    n=1e6;check[0]=check[1]=1;    for(int i=2;i<=n;i++){        if(!check[i]) prime[++tot]=i;        for(int j=1;j<=tot&&i*prime[j]<=n;j++){            check[i*prime[j]]=1;            if(!(i%prime[j])) break;        }     }}int main(){    freopen("count.in","r",stdin);    freopen("count.out","w",stdout);    pre();    scanf("%d%d%d",&n,&m,&p);    //全集     for(int k=1;k<=p;k++) sz[k]=m/p+(m%p>=k);sz[0]=sz[p];    for(int i=0;i<p;i++) f[1][i]=sz[i];    for(int i=1,val;i<n;i++){        for(int j=0;j<p;j++){            for(int k=0;k<p;k++){                val=(j+k)%p;                f[i+1&1][val]=(f[i+1&1][val]+sz[k]*f[i&1][j])%mod;            }        }        for(int j=0;j<p;j++) f[i&1][j]=0;    }    //不包含素数     for(int i=1;i<=tot&&prime[i]<=m;i++) sz[prime[i]%p]--;    for(int i=0;i<p;i++) g[1][i]=sz[i];    for(int i=1,val;i<n;i++){        for(int j=0;j<p;j++){            for(int k=0;k<p;k++){                val=(j+k)%p;                g[i+1&1][val]=(g[i+1&1][val]+sz[k]*g[i&1][j])%mod;            }        }        for(int j=0;j<p;j++) g[i&1][j]=0;    }    printf("%d",f[n&1][0]-g[n&1][0]);    return 0;}

#include<cstdio>#include<cstring>using namespace std;typedef long long ll;const int mod=20170408;const int N=101;const int M=2e7+5;int tot,prime[M/3];bool check[M];int n,m,p;int sz[N];struct matrix{    ll s[N];//降低常数     matrix(){        memset(s,0,sizeof s);    }}A,B;matrix operator *(const matrix &a,const matrix &b){    matrix c;    for(int i=0;i<p;i++){//        c.s[i]=0;        for(int k=0;k<p;k++){            c.s[i]+=a.s[(i-k+p)%p]*b.s[k];            c.s[i]%=mod;        }     }    return c;}ll fpow(matrix a,ll p){    matrix res;//    for(int i=0;i<p;i++) res.s[i]=0;    res.s[0]=1;    for(;p;p>>=1,a=a*a) if(p&1) res=res*a;    return res.s[0];}void pre(){    check[0]=check[1]=1;    for(int i=2;i<=m;i++){        if(!check[i]) prime[++tot]=i;        for(int j=1;j<=tot&&i*prime[j]<=m;j++){            check[i*prime[j]]=1;            if(!(i%prime[j])) break;        }     }}int main(){    freopen("count.in","r",stdin);    freopen("count.out","w",stdout);    scanf("%d%d%d",&n,&m,&p);    pre();    for(int k=1;k<=p;k++) sz[k]=m/p+(m%p>=k);sz[0]=sz[p];    for(int i=0;i<p;i++) A.s[i]=sz[i];    for(int i=1;i<=tot&&prime[i]<=m;i++) sz[prime[i]%p]--;    for(int i=0;i<p;i++) B.s[i]=sz[i];    ll ans=(fpow(A,n)-fpow(B,n))%mod;if(ans<0) ans+=mod;    printf("%lld",ans);    return 0;}