过了样例全WA

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring> 
using namespace std;
typedef long long ll;
ll n,m,p;
string a,b;
ll dp[2][150],g[2][150];
ll cnt[150],cur[150];
const ll mod=20170408;


bool pi[20000020];
ll tot,t[100010];
void prime(){
	pi[0]=pi[1]=1;
	cnt[1]=cur[1]=1;
	for(ll i=2;i<=m;i++){
		cnt[i%p]++;
		if(pi[i]){
			cur[i%p]++;
		}
		else{
			t[++tot]=i;
		}
		for(ll j=1;j<=tot;j++){
			if(t[j]*i>m){
				break;
			}
			pi[t[j]*i]=1;
			if(i%t[j]==0){
				break;
			}
		}
	}
}


struct matrix{
	int mt[150][150];
};
matrix mul(matrix a,matrix b){
	matrix c;
	for(int i=0;i<p;i++){
		for(int j=0;j<p;j++){
			for(int k=0;k<p;k++){
				c.mt[i][j]+=a.mt[i][k]*b.mt[k][j]%mod;
				c.mt[i][j]%=mod;
			}
		}
	}
	return c;
}
matrix mpow(matrix a,int p){
	if(p==1){
		return a;
	}
	matrix ans;
	if(p%2){
		ans=a;
		matrix sum=mpow(a,p/2);
		sum=mul(sum,sum);
		ans=mul(ans,sum);
	}
	else{
		ans=mpow(a,p/2);
		ans=mul(ans,ans);
	}
	return ans;
}


int main(){
	cin>>n>>m>>p;
	prime();
	matrix s,x;
	for(int i=0;i<p;i++){
		s.mt[i][0]=cnt[p-i];
		for(int j=0;j<p;j++){
			x.mt[i][j]=cnt[(p+j-i)%p];
		}
	}
	s=mul(mpow(x,n-1),s);
	matrix t=s;
	for(int i=0;i<p;i++){
		s.mt[i][0]=cur[p-i];
		for(int j=0;j<p;j++){
			x.mt[i][j]=cur[(p+j-i)%p];
		}
	}
	s=mul(mpow(x,n-1),s);
	cout<<t.mt[0][0]-s.mt[0][0];
	return 0;
}