前言：
应某人的要求，写一下题解。
这题折磨吗，不折磨，折磨吗，不折磨。所以宇宙万法的源头是什么？如如，所以折磨吗，如折。
解题思路：
首先，容易想到递推 $ n $ （矩乘不递推大的推什么？），枚举当前合法方案中的后缀再多出一个字符后是否会变的不合法。看到 $ m $ 的范围，尝试dp。
设 $ f_{i,j} $ 表示当前为第 $ i $ 位，有长度为 $ j $ 的不吉利数字的后缀的方案数，$ g_{i,j} $ 表示后缀长度为 $ i $ 的不吉利数字加上一个字符后变为后缀长度为 $ j $ 不吉利数字的方案数。我们就可以推出：
\[f_{i,j}= \sum_{k=0} ^{m}f_{i-1,k} \times g_{k,j} \]这里的 $ g_{k,j} $ 根据定义显然是可以预处理的。但是我的评价是：暴力处理甚至都没有KMP好想。前缀匹配后缀那可不就是KMP吗！所以直接上KMP。
再接下来就是构造矩阵了。首先，$ m $ 的长度很小，所以可以构造一个 $ m \times m $ 大小的矩阵：
\[\begin{bmatrix} f_{i,0}\\f_{i,1}\\ \vdots \\f_{i,m-1}\end{bmatrix} \]初态就是 $ f_{0,0}=1 $（空串），对应到矩阵上就是：
\[\begin{bmatrix}\,1 \,\\ \,0 \, \\ \, 0 \, \\ \, \vdots \, \\\,0 \, \end{bmatrix} \]最重要的就是如何构造操作矩阵了。因为是 $ f_{i-1,k} \times g_{k,j} \to f_{i,j} $ 的，所以是由第 $ k $ 个转移到第 $ j $ 个，也就是第 $ k $ 行和第 $ j $ 列。所以操作矩阵异常的简单，就是：
\[\begin{bmatrix}g_{0,0},g_{0,1},\cdots ,g_{0,m-1}\\g_{1,0},g_{1,1},\cdots ,g_{1,m-1}\\ \vdots \\ g_{m-1,0},g_{m-1,1}, \cdots ,g_{m-1,m-1} \end{bmatrix} \]上述即为：
\[\begin{bmatrix} f_{i+1,0}\\f_{i+1,1}\\ \vdots \\f_{i+1,m-1}\end{bmatrix} = \begin{bmatrix}g_{0,0},g_{0,1},\cdots ,g_{0,m-1}\\g_{1,0},g_{1,1},\cdots ,g_{1,m-1}\\ \vdots \\ g_{m-1,0},g_{m-1,1}, \cdots ,g_{m-1,m-1} \end{bmatrix} \times \begin{bmatrix} f_{i,0}\\f_{i,1}\\ \vdots \\f_{i,m-1}\end{bmatrix} \]代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define TP template<typename T>
#define TP_ template<typename T,typename ... T_>
TP void read(T &x)
{
x=0;int f=1;char ch=getchar();
for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
x*=f;
}
TP_ void read(T &x,T_&...y){read(x);read(y...);}
TP void write(T x){if(x<0){putchar('-'),x=-x;}if(x>9)write(x/10);putchar(48+x%10);}
TP void writeln(T x){if(x<0){putchar('-'),x=-x;}if(x>9)write(x/10);putchar(48+x%10);puts("");}
TP_ void writeln(const T x,T_ ...y){write(x);putchar(' ');writeln(y...);}
typedef long long LL;
int n,m,P;
char s[25];
int p[25];
int match[25][25];
struct matrix
{
LL a[25][25];
matrix()
{
memset(a,0,sizeof(a));
}
friend matrix operator *(const matrix &A,const matrix &B)
{
matrix C;
for(int i=1;i<=m;i++)
for(int j=1;j<=m;j++)
for(int k=1;k<=m;k++)
C.a[i][j]=(C.a[i][j]+A.a[i][k]*B.a[k][j]%P)%P;
return C;
}
}F,f;
matrix qpow(matrix a,LL b)
{
matrix ans;for(int i=1;i<=m;i++)ans.a[i][i]=1;
for(;b;b>>=1)
{
if(b&1)ans=ans*a;
a=a*a;
}
return ans;
}
void KMP()
{
int len=strlen(s+1);
p[1]=0;
for(int i=2,j=0;i<=len;i++)
{
while(j&&s[i]!=s[j+1])j=p[j];
if(s[i]==s[j+1])j++;
p[i]=j;
}
for(int i=0;i<m;i++)
{
for(int j='0';j<='9';j++)
{
int temp=i;
while(s[temp+1]!=j&&temp)temp=p[temp];
if(s[temp+1]==j)temp++;
match[i+1][temp+1]++;
}
}
}
int main()
{
read(n,m,P);
scanf("%s",s+1);
KMP();
for(int i=1;i<=m;i++)
for(int j=1;j<=m;j++)
f.a[i][j]=match[i][j];
F.a[1][1]=1;
LL ans=0;
F=F*qpow(f,n);
for(int i=1;i<=m;i++)
ans=(ans+F.a[1][i])%P;
writeln(ans);
return 0;
}