#include<bits/stdc++.h>
#define FILE "read"
#define MAXN (int)2e7+50
using namespace std;
typedef long long ll;
const int mod=20170408;
struct node{ll p[110][110];}a,zh;
int n,m,p,cnt,v[110],prime[MAXN];
bool check[MAXN];
ll ans[2];
inline int read(){
	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;
}
inline node operator*(node a,node b){
	node c;  memset(c.p,0,sizeof(c.p));
	for(int i=0;i<p;++i)
		for(int j=0;j<p;++j)
			for(int k=0;k<p;++k)
				c.p[i][j]=(c.p[i][j]+a.p[i][k]*b.p[k][j]%mod)%mod;
	return c;
} 
void pre(){
	for(int i=2;i<=m;++i){
		if(!check[i])  prime[++cnt]=i;
		for(int j=1;j<=cnt&&prime[j]*i<=m;++j){
			check[prime[j]*i]=1;
			if(i%prime[j]==0)  break;
		}
	}check[1]=1;
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	n=read();  m=read();  p=read();  pre();
	for(int i=1;i<=m;++i)if(check[i])v[i%p]++;
	for(int i=0;i<p;++i)for(int j=0;j<p;++j)(zh.p[i][(i+j)%p]+=v[j])%=mod;
	for(int i=0;i<p;++i)a.p[i][i]=1;
	for(int b=n;b;b>>=1,zh=zh*zh)if(b&1)a=a*zh;
	ans[0]=a.p[0][0];  
	memset(v,0,sizeof(v));
	memset(zh.p,0,sizeof(zh.p));
	memset(a.p,0,sizeof(a.p));
	for(int i=1;i<=m;++i)v[i%p]++;
	for(int i=0;i<p;++i)for(int j=0;j<p;++j)(zh.p[i][(i+j)%p]+=v[j])%=mod;
	for(int i=0;i<p;++i)a.p[i][i]=1;
	for(int b=n;b;b>>=1,zh=zh*zh)if(b&1)a=a*zh;
	ans[1]=a.p[0][0];
	printf("%lld\n",(ans[1]-ans[0]+mod)%mod);
	return 0;
}