先用KMP处理所有的转移，或者直接暴力也可以。
然后矩阵快速幂即可。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define F(i,j,k) for (ll i=j;i<=k;++i)
#define D(i,j,k) for (ll i=j;i>=k;--i)
#define ll long long
ll n,m,md;
char s[50];
ll fail[50];
struct matrix{
ll x[25][25];
void init(){memset(x,0,sizeof x);}
void build1()
{
init();
x[0][0]=1;
}
void build2()
{
init();
F(i,0,m-1) F(j,0,9)
{
ll now=i;
while (now&&s[now+1]-'0'!=j) now=fail[now];
if (s[now+1]-'0'==j) now++;
x[i][now]++;
}
}
matrix operator * (matrix a) {
matrix ret;ret.init();
F(i,0,m-1) F(j,0,m-1)
{
F(k,0,m-1)
ret.x[i][j]+=x[i][k]*a.x[k][j];
ret.x[i][j]%=md;
}
return ret;
}
void print()
{
printf("---
");
F(i,0,m)
{
F(j,0,m) printf("%lld ",x[i][j]);
printf("
");
}
printf("---
");
}
void build3()
{
init();
F(i,0,m-1) x[i][i]=1;
}
}B,A,C;
int main()
{
scanf("%lld%lld%lld",&n,&m,&md);
scanf("%s",s+1);
for (int i=2,j=0;i<=m;++i)
{
while (j&&s[j+1]!=s[i]) j=fail[j];
if (s[j+1]==s[i]) j++;
fail[i]=j;
}
A.build1();B.build2();C.build3();
while (n)
{
if (n&1) C=C*B;
B=B*B;
n>>=1;
}
A=A*C;
int ans=0;
F(i,0,m-1) (ans+=A.x[0][i])%=md;
printf("%d
",ans);
}