// luogu-judger-enable-o2
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

int readint(){
	int x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

const int cys=20170408;
int n,m,p,tot,ret;
int A[105],B[105],ans[105],prime[10000005];
bool fl[20000005];

int mod(int x){return x>=p?x-p:x;}

void mul(int *A,int *B,int *C){
	memset(ans,0,sizeof(ans));
	for(int i=0;i<p;i++) for(int j=0;j<p;j++) ans[mod(i+j)]=(ans[mod(i+j)]+1ll*B[i]*C[j]%cys)%cys;
	for(int i=0;i<p;i++) A[i]=ans[i];
}

void solve(int p){for(;p;p>>=1,mul(B,B,B)) if(p&1) mul(A,A,B);}

void getprime(int g){
	fl[1]=true;
	for(int i=2;i<=g;i++){
		if(!fl[i]) prime[++tot]=i;
		for(int j=1;j<=tot&&i*prime[j]<=g;j++){
			fl[i*prime[j]]=true;
			if(i%prime[j]==0) break;
		}
	}
}

int main(){
	n=readint(); m=readint(); p=readint();
	getprime(m);
	for(int i=0;i<p;i++) A[i]=B[i]=m/p+(m%p>=i)-(i==0);
	solve(n-1);
	ret=A[0];
//	cout<<"TEST "<<ret<<endl;
	for(int i=0;i<p;i++) A[i]=B[i]=m/p+(m%p>=i)-(i==0);
	for(int i=1;i<=m;i++) if(!fl[i]) A[i%p]--,B[i%p]--;
	solve(n-1);
	printf("%d\n",(ret-A[0]+cys)%cys);
	return 0;
}