水题
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long ll;
int n, m, p, cnt[105], pri[2000005], ppp, ans=0;
const int mod=20170408;
bool isp[20000005];
struct Matrix{
int num[105][105];
Matrix operator*(const Matrix &x)const{
Matrix re;
for(int i=0; i<p; i++)
for(int j=0; j<p; j++){
re.num[i][j] = 0;
for(int k=0; k<p; k++)
re.num[i][j] = (re.num[i][j] + (ll)num[i][k]*x.num[k][j]) % mod;
}
return re;
}
}yua, dan, zhu;
Matrix ksm(Matrix a, int b){
Matrix re=dan;
while(b){
if(b&1) re = re * a;
a = a * a;
b >>= 1;
}
return re;
}
void shai(){
memset(isp, true, sizeof(isp));
isp[0] = isp[1] = false;
for(int i=2; i<=m; i++){
if(isp[i]) pri[++ppp] = i;
for(int j=1; j<=ppp && (ll)i*pri[j]<=m; j++){
isp[i*pri[j]] = false;
if(i%pri[j]==0) break;
}
}
}
int main(){
cin>>n>>m>>p;
shai();
for(int i=1; i<=m; i++)
cnt[i%p]++;
yua.num[0][0] = 1;
for(int i=0; i<p; i++){
dan.num[i][i] = 1;
for(int j=0; j<p; j++)
zhu.num[i][j] = cnt[((i-j)%p+p)%p];
}
ans = (yua*ksm(zhu, n)).num[0][0];
for(int i=1; i<=ppp; i++)
cnt[pri[i]%p]--;
for(int i=0; i<p; i++){
dan.num[i][i] = 1;
for(int j=0; j<p; j++)
zhu.num[i][j] = cnt[((i-j)%p+p)%p];
}
ans = ((ans - (yua*ksm(zhu, n)).num[0][0])%mod + mod) % mod;
cout<<ans<<endl;
return 0;
}