#include <cctype>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <array>
#include <bitset>
#include <deque>
#include <functional>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
#define bool signed char
typedef short i16;typedef unsigned short u16;
typedef int i32;typedef unsigned u32;
typedef long long i64;typedef unsigned long long u64;
typedef float f32;typedef double f64;

template<typename T>
class matrix{
	public:
		u32 n,m;
		i64 mo;
	private:
		T **a;
		void __init__(){if(a){T **i(a),**e(a+n);for(;i!=e;delete[] *i++);delete[] a;a=nullptr;n=m=0;mo=0;}}
	public:
		matrix():n(0),m(0),mo(0),a(nullptr){}~matrix(){__init__();}
		T* operator[](u32 k){return a[k];}
		const T* operator[](u32 k)const{return a[k];}
		void init(u32 _n,u32 _m,i64 _mo=0){
			__init__();
			n=_n;m=_m;mo=_mo;
			a=new T*[n];
			const u32 sz(m*sizeof(T));
			for(T **i(a),**e(a+n);i!=e;++i){
				*i=new T[m];
				memset(*i,0,sz);
			}
		}
		matrix(u32 _n,u32 _m,i64 _mo=0):n(0),m(0),mo(0),a(nullptr){init(_n,_m,_mo);}
		matrix(const matrix<T>& other):n(other.n),m(other.m),mo(other.mo),a(nullptr){
			if(n&&m){
				a=new T*[n];
				for(T **i(a),**e(a+n),**j(other.a);i!=e;++i,++j){
					*i=new T[m];
					std::copy(*j,*j+m,*i);
				}
			}
		}
		matrix(matrix&& other):n(other.n),m(other.m),mo(other.mo),a(other.a){
			other.n=other.m=other.mo=0;other.a=nullptr;
		}
		matrix<T>& operator=(const matrix<T>& other){
			if(this!=&other){
				__init__();
				n=other.n;m=other.m;mo=other.mo;
				if(n&&m){
				a=new T*[n];
					for(T **i(a),**e(a+n),**j(other.a);i!=e;++i,++j){
						*i=new T[m];
						std::copy(*j,*j+m,*i);
					}
				}
			}
			return *this;
		}
		matrix<T>& operator=(matrix<T>&& other){
			if(this!=&other){
				__init__();
				n=other.n;m=other.m;a=other.a;mo=other.mo;
				other.n=0;other.m=0;other.a=nullptr;other.mo=0;
			}
			return *this;
		}
		matrix<T> operator+(const matrix<T>& other){
			if(n!=other.n||m!=other.m){
				fprintf(stderr,"Invalid size.\n");
				exit(-1);
			}else if(mo!=other.mo){
				fprintf(stderr,"mod number is different.\n");
				exit(-1);
			}
			matrix<T> b(other);
			if(mo){
				for(T **i(b.a),**e(b.a+n),**j(a),*i1,*e1,*j1;i!=e;++i,++j)
					for(i1=*i,e1=i1+m,j1=*j;i1!=e1;++i1,++j1)
						*i1=(*i1+*j1)%mo;
			}else{
				for(T **i(b.a),**e(b.a+n),**j(a),*i1,*e1,*j1;i!=e;++i,++j)
					for(i1=*i,e1=i1+m,j1=*j;i1!=e1;++i1,++j1)
						*i1+=*j1;
			}
			return b;
		}
		matrix<T> operator+(matrix<T>&& other){
			if(n!=other.n||m!=other.m){
				fprintf(stderr,"Invalid size.\n");
				exit(-1);
			}else if(mo!=other.mo){
				fprintf(stderr,"mod number is different.\n");
				exit(-1);
			}
			matrix<T> b(other);
			if(mo){
				for(T **i(b.a),**e(b.a+n),**j(a),*i1,*e1,*j1;i!=e;++i,++j)
					for(i1=*i,e1=i1+m,j1=*j;i1!=e1;++i1,++j1)
						*i1=(*i1+*j1)%mo;
			}else{
				for(T **i(b.a),**e(b.a+n),**j(a),*i1,*e1,*j1;i!=e;++i,++j)
					for(i1=*i,e1=i1+m,j1=*j;i1!=e1;++i1,++j1)
						*i1+=*j1;
			}
			return b;
		}
		matrix<T> operator*(const matrix<T>& other){
			if(m!=other.n){
				fprintf(stderr,"Invalid size.\n");
				exit(-1);
			}else if(mo!=other.mo){
				fprintf(stderr,"mod number is different.\n");
				exit(-1);
			}
			matrix<T> b(n,other.m,mo);
			if(mo){
				for(u32 i,j,k(0);k<m;++k)
					for(i=0;i<n;++i)
						for(j=0;j<other.m;++j)
							b[i][j]=(b[i][j]+a[i][k]*other[k][j])%mo;
			}else{
				for(u32 i,j,k(0);k<m;++k)
					for(i=0;i<n;++i)
						for(j=0;j<other.m;++j)
							b[i][j]+=a[i][k]*other[k][j];
			}
			return b;
		}
		matrix<T> operator*(matrix<T>&& other){
			if(m!=other.n){
				fprintf(stderr,"Invalid size.\n");
				exit(-1);
			}else if(mo!=other.mo){
				fprintf(stderr,"mod number is different.\n");
				exit(-1);
			}
			matrix<T> b(n,other.m,mo);
			if(mo){
				for(u32 i,j,k(0);k<m;++k)
					for(i=0;i<n;++i)
						for(j=0;j<other.m;++j)
							b[i][j]=(b[i][j]+a[i][k]*other[k][j])%mo;
			}else{
				for(u32 i,j,k(0);k<m;++k)
					for(i=0;i<n;++i)
						for(j=0;j<other.m;++j)
							b[i][j]+=a[i][k]*other[k][j];
			}
			return b;
		}
		matrix<T> qpow(i64 b){
			if(n!=m){
				fprintf(stderr,"Invalid size.\n");
				exit(-1);
			}
			matrix<T> a(*this),r(n,n,mo);
			for(u32 i(0);i<n;++i){
				r[i][i]=1;
			}
			for(;b;b>>=1,a=a*a){
				if(b&1){
					r=r*a;
				}
			}
			return r;
		}
};
#define A 105
#define mo 20170408
int n,m,p,cnt[A];

void sieve_prime(int n){
	std::vector<bool> vs(n+1,false);
	std::vector<int> pm;
	int i;
	cnt[1%p]=1;
	for(i=2;i<=n;++i){
		if(!vs[i]){
			pm.push_back(i);
		}else{
			++cnt[i%p];
		}
		for(auto& j:pm){
			if(i*j>n)break;
			vs[i*j]=true;
			if(!(i%j))break;
		}
	}
}
int main(){
	int i,j,ans;
	scanf("%d%d%d",&n,&m,&p);
	matrix<i64> a(p,1,mo),b(p,p,mo);
	sieve_prime(m);
	for(i=0;i<p;++i){
		a[i][0]=cnt[i];
		for(j=0;j<p;++j){
			b[i][j]=cnt[(i-j+p)%p];
		}
	}
	a=b.qpow(n-1)*a;
	ans=mo-a[0][0];
	for(i=0;i<p;++i){
		cnt[i]=m/p+(i<m%p);
	}
	for(i=0;i<p;++i){
		a[i][0]=cnt[i];
		for(j=0;j<p;++j){
			b[i][j]=cnt[(i-j+p)%p];
		}
	}
	a=b.qpow(n-1)*a;
	ans=(ans+a[0][0])%mo;
	printf("%d\n",ans);
	return 0;
}