题目链接：GT考试

---

设 dp[i][j] 为第一个串到位置 i ，第二个串到位置 j 的方案数。
然后：dp[i][j] = dp[i][k] * g[k][j] g数组 g[i][j] 表示，从i位置到j的方案数。

然后这个可以ac自动机或者kmp预处理，然后做一个矩阵快速幂即可。

---

AC代码：

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=22;
int n,m,mod,c[N][10],fail[N],idx,ed[N],res; char str[N];
struct mat{int g[N][N];}s,a;
void mul(mat &a,mat b){
	mat c; memset(c.g,0,sizeof c.g);
	for(int i=0;i<=idx;i++)
		for(int j=0;j<=idx;j++)
			for(int k=0;k<=idx;k++)
				c.g[i][j]=(c.g[i][j]+a.g[i][k]*b.g[k][j])%mod;
	a=c;
}
void insert(){
	int p=0;
	for(int i=1;str[i];i++){
		int k=str[i]-'0';
		if(!c[p][k]) c[p][k]=++idx;
		p=c[p][k];
	}
	ed[p]=1;
}
void build(){
	queue<int> q;
	for(int i=0;i<10;i++) if(c[0][i]) q.push(c[0][i]);
	while(q.size()){
		int u=q.front(); q.pop();
		ed[u]|=ed[fail[u]];
		for(int i=0;i<10;i++)
			if(c[u][i]) fail[c[u][i]]=c[fail[u]][i],q.push(c[u][i]);
			else c[u][i]=c[fail[u]][i];
	}
}
signed main(){
	scanf("%d %d %d %s",&n,&m,&mod,str+1);
	insert(),build();
	for(int i=0;i<=idx;i++) for(int j=0;j<10;j++)
		if(!ed[i]&&!ed[c[i][j]])  a.g[i][c[i][j]]++;
	s.g[0][0]=1;
	for(;n;n>>=1,mul(a,a)) if(n&1) mul(s,a);
	for(int i=0;i<=m;i++) res=(res+s.g[0][i])%mod;
	cout<<res;
	return 0;
}