4 3 100
111

81

# 题目分析

i=0m1dp(n,i)

dp(i,j)=k=0m1(dp(i1,k)×p(k,j))

DPi=DPi1×P

DPn=DPn1×P=DP0×Pn

# 代码

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 22;
int MOD, Fail[MAXN+10];
char s[MAXN+10];
struct Matrix {
int Ma[MAXN+10][MAXN+10], n, m;
void Clear(int u, int un=0, int um=0){
n = un, m = um;
for(int i=0;i<un;i++)
for(int j=0;j<um;j++)
Ma[i][j] = 0;
if(u) for(int i=0;i<un;i++)
Ma[i][i] = 1;
}
Matrix operator* (const Matrix& ma) {
Matrix ret ;
ret.Clear(0, n, m);
for(int i=0;i<n;i++){
for(int j=0;j<ma.m;j++){
for(int k=0;k<ma.n;k++){
ret.Ma[i][j] += Ma[i][k] * ma.Ma[k][j];
ret.Ma[i][j] %= MOD;
}
}
}
return ret;
}
};
Matrix Mpow(Matrix m, int p){
Matrix ret;
if(p == 0){
ret.Clear(1, 2, 2);
return ret;
}else if(p == 1) return m;
ret = Mpow(m, p/2);
if(p%2 == 0) return ret * ret;
return (ret * ret) * m;
}
int main(){
int n, m;
scanf("%d%d%d", &n, &m, &MOD);
scanf("%s", s+1);
Matrix mtr;
mtr.Clear(0, m, m);
mtr.Ma[0][0] = 9;
mtr.Ma[0][1] = 1;
for(int i=1;i<m;i++){
int us = Fail[i];
while(us){
if(s[us+1] == s[i+1])
break;
us = Fail[us];
}
if(s[us+1] == s[i+1])
Fail[i+1] = us+1;
else Fail[i+1] = 0;
for(int j=0;j<=9;j++){
int u = i;
while(u&&s[u+1] != j+'0') u = Fail[u];
if(s[u+1] == j+'0') mtr.Ma[i][u+1] = (mtr.Ma[i][u+1] + 1) % MOD;
else mtr.Ma[i][0] = (mtr.Ma[i][0] + 1) % MOD;
}
}
Matrix ans = Mpow(mtr, n);
int anst = 0;
for(int i=0;i<m;i++)
anst = (anst + ans.Ma[0][i]) % MOD;
printf("%d\n", (anst+MOD)%MOD);

return 0;
}