传送门

求方案数，显然这个题得动态规划。。。

设$f(i,j)$为母串长为$i$位，子串当前匹配到了第$j$位的方案数。考虑$f(i,j)$向$i+1$转移：

枚举$i+1$的数字，然后就会发现这玩意可以用$kmp$转移。预处理出$next$数组后，转移时和普通的$kmp$匹配一样跳$next$数组，直到匹配到最长前缀转移过去。

初值$f(0,0)=1$，答案$ans=\sum\limits_{i=0}^{i<m}f(n,i)$

伪代码：

    f[0][0]=1;
    for(int i=0;i<n;++i)
        for(int j=0;j<m;++j)
            for(int k='0';k<='9';++k){//枚举下一位
                int l=j;
                while(l&&a[l+1]!=k)l=next[l];
                if(a[l+1]==k)++l;
                //和kmp一样以k为i+1位的数字匹配
                (f[i+1][l]+=f[i][j])%=mod;
            }
    int ans=0;
    for(int i=0;i<m;++i)
        (ans+=f[n][i])%=mod;

复杂度不会证，反正不低于$O(10nm)$。这个式子可以用矩阵快速幂优化。把$f(i-1,0$ ~ $m-1)$和$f(i,0$ ~ $m-1)$扔进去，枚举每一个$j$和第$i+1$位的数字，在矩阵上对应的位置$+1$。

显然$f(1,0)=9,f(1,1)=1$，然后直接矩乘就好了。

矩阵大小：$(2m)*(2m)$，复杂度$O(40^3\log n)$

代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>

using namespace std;

inline int read(){
    int x=0,y=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return y?-x:x;
}
template<typename T>
inline T read(){
    T x=0;
    int y=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return y?-x:x;
}
int n,m,mod;
int next[50];
char a[22];
struct Matrix{
    int a[50][50],l,c;
    Matrix operator * (const Matrix x){
        Matrix ans;
        ans.l=l,ans.c=x.c;
        for(register int k=0;k<c;++k)
            for(register int i=0;i<l;++i)
                for(register int j=0;j<x.c;++j)
                    (ans.a[i][j]+=a[i][k]*x.a[k][j])%=mod;
        return ans;
    }
    Matrix(){
        memset(a,0,sizeof a);
    }
}start,origin;
//start为初始矩阵，origin为转移矩阵
Matrix quickpow(Matrix x,int y){
    Matrix ans;
    ans.l=ans.c=x.l;
    for(register int i=0;i<ans.l;++i)
        ans.a[i][i]=1;
    while(y){
        if(y&1)ans=ans*x;
        x=x*x;
        y>>=1;
    }
    return ans;
}
void kmp(){
    int j=0;
    for(register int i=2;i<=m;++i){
        while(j&&a[j+1]!=a[i])j=next[j];
        if(a[j+1]==a[i])++j;
        next[i]=j;
    }
}
void build(){
    for(register int i=m,j=0;i<(m<<1);++i,++j)
        origin.a[i][j]=1;
    for(register int i=0;i<m;++i){
        for(register int j='0';j<='9';++j){
            int k=i;
            while(k&&a[k+1]!=j)k=next[k];
            if(a[k+1]==j)++k;
            if(k<m)++origin.a[i+m][k+m];
            //m=i、下一位为j时会对第k位产生影响
        }
    }
    origin.l=origin.c=m<<1;
    start.l=1,start.c=m<<1;
    start.a[0][0]=start.a[0][m+1]=1,start.a[0][m]=9;
}
int main(){
    n=read(),m=read(),mod=read();    
    scanf("%s",a+1);
    kmp();
    build();
    start=start*quickpow(origin,n);
    int ans=0;
    for(register int i=0;i<m;++i)
        (ans+=start.a[0][i])%=mod;
    printf("%d\n",ans);
}