记录编号	414781	评测结果	AAAAAAAAAA
题目名称	[HNOI 2008]GT考试	最终得分	100
用户昵称	Hzoi_Ivan	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2017-06-14 21:48:14	内存使用	0.00 MiB

#define fastcall __attribute__((optimize("-O3"))) 
#include<cstdio>
#include<cstring>
#include<iostream>
#define N 22
using namespace std;
int n,m,mod,ans,A[N][N],B[N][N],nxt[N];
char s[N];
void mul(int a[22][22],int b[22][22],int c[22][22])
{
     int d[22][22];
     for(int i=0;i<m;i++)
       for(int j=0;j<m;j++)
       {
          d[i][j]=0;
          for(int k=0;k<m;k++)
            d[i][j]=(d[i][j]+a[i][k]*b[k][j])%mod;
       }
     for(int i=0;i<m;i++)
       for(int j=0;j<m;j++)
         c[i][j]=d[i][j];
}
void kmp(){
	for(int i=0;i<m;i++)
    {
      for(int j=0;j<=9;j++)
      {
        int ii=i;
        while(~ii&&s[ii+1]-'0'!=j) ii=nxt[ii];
        ii++;
        A[ii][i]++;
        A[ii][i]%=mod;
      } 
    }
}
int haha(){
	freopen("bzoj_1009.in","r",stdin);
    freopen("bzoj_1009.out","w",stdout);
    scanf("%d%d%d",&n,&m,&mod);
    scanf("%s",s+1);
    nxt[0]=-1; nxt[1]=0;
    for(int i=2,j=0;i<=m;i++){
      while(~j&&s[i]!=s[j+1]) j=nxt[j];
      nxt[i]=++j;
    }
    kmp();
    for(int i=0;i<m;i++)
      B[i][i]=1;
    while(n)
    {
      if(n&1) mul(A,B,B);
      mul(A,A,A);
      n>>=1;
    }
    for(int i=0;i<m;i++)
      ans=(ans+B[i][0])%mod;
    printf("%d\n",ans);
    return 0;
}
int sb=haha();
int main(){;}