题解
构造状态转移图，用矩阵优化DP。
状态转移图是现成的，就是KMP的匹配图。
按照这个对每一个点处理：
把模式串每一位看作一个点，最开始也加一个点（0号点，表示匹配不到模式串的任何一个点）
每一个点都有0-9共9条边，每个点（除了最后一个点）都向下一个点连一条相应数字边，然后最初的0号点就只有9个自环边。
之后每一个点（除了最后一个）能往前转移就往前转，转不了就转到0号点上去。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
using namespace std;
typedef long long ll;
int n,m,Mod,fail[55],ans=0;
char danger[55];
struct Mat{
int dat[22][22];
int r,c;
Mat(){
memset(dat,0,sizeof(dat));
}
};
Mat mul(Mat &a,Mat &b){
Mat newed;
newed.r=a.r,newed.c=b.c;
int i,j,k,t;
for(i=0;i<a.r;i++)
for(j=0;j<b.c;j++){
for(t=0,k=0;k<a.c;k++)t+=(a.dat[i][k])*(b.dat[k][j]),t%=Mod;
newed.dat[i][j]=t%Mod;
}
return newed;
}
Mat Pow(Mat a,ll p){
Mat E;E.r=E.c=a.c;
int i,j;
for(i=0;i<a.c;i++)
for(j=0;j<a.c;j++)
E.dat[i][j]=(i==j)?1:0;
while(p){
if(p&1)E=mul(E,a);
a=mul(a,a),p>>=1;
}
return E;
}
int mat[21][21];
void build_fail(char *pat,int l,int *fail){
fail[0]=-1;
for(int i=1,j=-1;i<l;i++){
for(;j>-1&&pat[i]!=pat[j+1];j=fail[j]);
if(pat[i]==pat[j+1]&&i>j+1)
fail[i]=++j;
else
fail[i]=-1;
}
}
void init(){
scanf("%d%d%d%s",&n,&m,&Mod,danger);
build_fail(danger,m,fail);
}
void solve(){
Mat Ori,Plu,res;
Ori.r=Plu.r=Plu.c=m+1;
Ori.c=1;
Plu.dat[0][0]=9,Plu.dat[1][0]=1;
bool used[10];
int CNT=10;
for(int i=1;i<m;i++){
int f=i-1,flag=0;
memset(used,0,sizeof(used));
CNT=10;
do{
f=fail[f];
if(danger[f+1]!=danger[i]){
if(!used[danger[f+1]-'0'])
used[danger[f+1]-'0']=1,
Plu.dat[f+2][i]=1,
CNT--;
}
}while(f!=-1);
Plu.dat[i+1][i]=1;
CNT--;
Plu.dat[0][i]=CNT;
}
for(int i=0;i<=m;i++)
Plu.dat[m][i]=0;
Ori.dat[0][0]=1;
Plu=Pow(Plu,n);
res=mul(Plu,Ori);
for(int i=0;i<m;i++)
ans=(ans+res.dat[i][0])%Mod;
printf("%d\n",ans);
}
int main(){
init();
solve();
return 0;
}