//f[i][j][1/0]表示长为i,sum mod p=j,是否已经选了质数的方案数

#include<cstdio>

using namespace std;

const int mod=;

const int N=1e6+;

int tot,prime[N/];bool check[N];

int n,m,f[][N][];int p;

void pre(){

    n=1e6;check[]=check[]=;

    for(int i=;i<=n;i++){

        if(!check[i]) prime[++tot]=i;

        for(int j=;j<=tot&&i*prime[j]<=n;j++){

            check[i*prime[j]]=;

            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=;i<=m;i++) f[][i%p][!check[i]]++;

    for(int i=,val;i<n;i++){

        for(int j=;j<p;j++){

            for(int k=;k<=m;k++){

                val=(j+k)%p;

                if(!check[k]){

                    f[i+&][val][]=(f[i+&][val][]+f[i&][j][]+f[i&][j][])%mod;

                }

                else{

                    f[i+&][val][]=(f[i+&][val][]+f[i&][j][])%mod,

                    f[i+&][val][]=(f[i+&][val][]+f[i&][j][])%mod;

                }

            }

        }

        for(int j=;j<p;j++){

            f[i&][j][]=;

            f[i&][j][]=;

        }

    }

    printf("%d",f[n&][][]);

    return ;

}

#include<cstdio>

using namespace std;

const int mod=;

const int N=1e6+;

int tot,prime[N/];bool check[N];

int n,m,p;

int f[][N];

int g[][N];

int sz[N];

void pre(){

    n=1e6;check[]=check[]=;

    for(int i=;i<=n;i++){

        if(!check[i]) prime[++tot]=i;

        for(int j=;j<=tot&&i*prime[j]<=n;j++){

            check[i*prime[j]]=;

            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=;k<=p;k++) sz[k]=m/p+(m%p>=k);sz[]=sz[p];

    for(int i=;i<p;i++) f[][i]=sz[i];

    for(int i=,val;i<n;i++){

        for(int j=;j<p;j++){

            for(int k=;k<p;k++){

                val=(j+k)%p;

                f[i+&][val]=(f[i+&][val]+sz[k]*f[i&][j])%mod;

            }

        }

        for(int j=;j<p;j++) f[i&][j]=;

    }

    //不包含素数

    for(int i=;i<=tot&&prime[i]<=m;i++) sz[prime[i]%p]--;

    for(int i=;i<p;i++) g[][i]=sz[i];

    for(int i=,val;i<n;i++){

        for(int j=;j<p;j++){

            for(int k=;k<p;k++){

                val=(j+k)%p;

                g[i+&][val]=(g[i+&][val]+sz[k]*g[i&][j])%mod;

            }

        }

        for(int j=;j<p;j++) g[i&][j]=;

    }

    printf("%d",f[n&][]-g[n&][]);

    return ;

}

#include<cstdio>

#include<cstring>

using namespace std;

typedef long long ll;

const int mod=;

const int N=;

const int M=2e7+;

int tot,prime[M/];bool check[M];

int n,m,p;

int sz[N];

struct matrix{

    ll s[N];//降低常数

    matrix(){

        memset(s,,sizeof s);

    }

}A,B;

matrix operator *(const matrix &a,const matrix &b){

    matrix c;

    for(int i=;i<p;i++){

//        c.s[i]=0;

        for(int k=;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[]=;

    for(;p;p>>=,a=a*a) if(p&) res=res*a;

    return res.s[];

}

void pre(){

    check[]=check[]=;

    for(int i=;i<=m;i++){

        if(!check[i]) prime[++tot]=i;

        for(int j=;j<=tot&&i*prime[j]<=m;j++){

            check[i*prime[j]]=;

            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=;k<=p;k++) sz[k]=m/p+(m%p>=k);sz[]=sz[p];

    for(int i=;i<p;i++) A.s[i]=sz[i];

    for(int i=;i<=tot&&prime[i]<=m;i++) sz[prime[i]%p]--;

    for(int i=;i<p;i++) B.s[i]=sz[i];

    ll ans=(fpow(A,n)-fpow(B,n))%mod;if(ans<) ans+=mod;

    printf("%lld",ans);

    return ;

}