设f[i][j]是到第i位 已经匹配上了j位的状态数 然后通过枚举下一位放0~9，可以用kmp处理出一个转移的矩阵
然后就可以矩阵快速幂了
#include<bits/stdc++.h>
#define pa pair<int,int>
#define CLR(a,x) memset(a,x,sizeof(a))
using namespace std;
typedef long long ll;
const int maxm=; inline ll rd(){
ll x=;char c=getchar();int neg=;
while(c<''||c>''){if(c=='-') neg=-;c=getchar();}
while(c>=''&&c<='') x=x*+c-'',c=getchar();
return x*neg;
} int N,M,K,trans[maxm][maxm],ans[maxm][maxm],tmp[maxm][maxm],fail[maxm];
char x[maxm]; inline void mul(int a[][maxm],int b[][maxm]){
for(int i=;i<M;i++){
for(int j=;j<M;j++){
tmp[i][j]=;
for(int k=;k<M;k++){
tmp[i][j]+=a[i][k]*b[k][j],tmp[i][j]%=K;
}
}
}
} inline void modp(int b){
while(b){
if(b&) mul(ans,trans),memcpy(ans,tmp,sizeof(ans));
mul(trans,trans),memcpy(trans,tmp,sizeof(tmp));
b>>=;
}
} int main(){
//freopen("","r",stdin);
int i,j,k;
N=rd(),M=rd(),K=rd();
scanf("%s",x+);
for(i=,j=;i<=M;i++){
while(j&&x[i]!=x[j+]) j=fail[j];
if(x[i]==x[j+]) j++;
fail[i]=j;
}
for(i=;i<M;i++){
for(j='';j<='';j++){
int k=i;
while(k&&j!=x[k+]) k=fail[k];
if(j==x[k+]) k++;
if(k<M) trans[i][k]++;
}
}
ans[][]=,ans[][]=;
modp(N-);
int p=;
for(i=;i<M;i++) p+=ans[][i];
printf("%d\n",p%K);
return ;
}