这道到是不用看题解，不过太经典了，早就被剧透一脸了
这道题很像ac自动机上的dp（其实就是）
然后注意到n很大，节点很小，于是就可以用矩阵快速幂优化了
时间复杂度为o(m^3 *log n);
蒟蒻kpm写得少，改了好久= =
CODE：
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,mod;
#define maxn 30
char c[maxn];
struct martix{
int r,c;int f[maxn][maxn];
int init(int x){
r=c=x;
for (int i=1;i<=x;i++) f[i][i]=1;
}
}a,b;
martix operator * (const martix &x,const martix &y){
martix ans;
ans.r=x.r;
ans.c=y.c;
for (int i=1;i<=ans.r;i++)
for (int j=1;j<=ans.c;j++){
ans.f[i][j]=0;
for (int k=1;k<=x.c;k++)
ans.f[i][j]=((x.f[i][k]*y.f[k][j])%mod+ans.f[i][j])%mod;
}
return ans;
}
martix quick(int x,martix y){
martix ans;
ans.init(y.r);
for (;x;x>>=1){
if (x&1) ans=ans*y;
y=y*y;
}
return ans;
}
int next[maxn];
int main(){
scanf("%d%d%d",&n,&m,&mod);
scanf("%s",c+1);
int t=0;
next[1]=0;
for (int i=2;i<=m;i++) {
while (t&&c[t+1]!=c[i]) t=next[t];
next[i]=c[t+1]!=c[i]?0:++t;
}
a.r=a.c=m+1;
for (int i=1;i<=m;i++) a.f[i][i+1]=1;
a.f[1][1]=9;
for (int i=1;i<m;i++) {
int sum=1;
{
for (int j=2;j<=m+1;j++)
if (a.f[next[i]+1][j]&&c[j-1]!=c[i+1]){
a.f[i+1][j]=a.f[next[i]+1][j];sum+=a.f[i+1][j];
}
}
a.f[i+1][1]=10-sum;
}
a=quick(n,a);
b.r=1;b.c=1+m;
b.f[1][1]=1;
a=b*a;
int ans=0;
for (int i=1;i<=m;i++) (ans+=a.f[1][i])%=mod;
printf("%d",ans);
return 0;
}