#include<bits/stdc++.h>

 using namespace std;

 const int maxn = ;

 const int mod = ;

 int n,m,q;

 int base[][];

 int flag[maxn],prime[maxn/],num;

 int mat[][],Res[][],po[][];

 void init(){

     flag[] = ;

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

     if(!flag[i]) prime[++num] = i;

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

         flag[i*prime[j]] = ;

         if(i%prime[j] == ) break;

     }

     }

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

     if(flag[i]) base[i%q][]++;

     base[i%q][]++;

     }

 }

 void BuildMatrix(int now){

     memset(mat,,sizeof(mat));

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

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

         int nw = j-i;if(nw < ) nw += q;

         mat[j][nw] += base[i][now];

     }

     }

 }

 void fast_pow(int now){

     if(now == ){

     for(int i=;i<q;i++) for(int j=;j<q;j++) Res[i][j]=mat[i][j];

     }else{

     fast_pow(now/);

     memset(po,,sizeof(po));

     for(int k=;k<q;k++)

         for(int i=;i<q;i++)

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

             po[i][j] += (1ll*Res[i][k]*Res[k][j])%mod;

             po[i][j] %= mod;

         }

     for(int i=;i<q;i++)for(int j=;j<q;j++)Res[i][j]=po[i][j];

     if(now & ){

         memset(po,,sizeof(po));

         for(int k=;k<q;k++)

         for(int i=;i<q;i++)

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

             po[i][j] += (1ll*Res[i][k]*mat[k][j])%mod;

             po[i][j] %= mod;

             }

         for(int i=;i<q;i++)for(int j=;j<q;j++)Res[i][j]=po[i][j];

     }

     }

 }

 void work(){

     BuildMatrix();

     fast_pow(n);

     int ans = Res[][];

     BuildMatrix();

     fast_pow(n);

     ans -= Res[][];

     if(ans < ) ans += mod;

     printf("%d",ans);

 }

 int main(){

     scanf("%d%d%d",&n,&m,&q);

     init();

     work();

     return ;

 }