阿申准备报名参加GT考试，准考证号为N位数X1X2....Xn(0<=Xi<=9),他不希望准考证号上出现不吉利的数字。
他的不吉利数学A1A2...Am(0<=Ai<=9)有M位，不出现是指X1X2...Xn中没有恰好一段等于A1A2...Am.
A1和X1可以为
0

　　第一行输入N,M,K.接下来一行输入M位的数。 N<=10^9,M<=20,K<=1000

　　阿申想知道不出现不吉利数字的号码有多少种，输出模K取余的结果.

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

using namespace std;

int n,m,p,next[],an; char S[];

struct Matrixnode

{

    int da[][];

    Matrixnode(){memset(da,,sizeof(da));}

}a;

Matrixnode Mul (Matrixnode A,Matrixnode B)

{

    Matrixnode C;

    for (int i=; i<m; i++)

        for (int j=; j<m; j++)

            for (int k=; k<m; k++)

                C.da[i][j]=(C.da[i][j]+A.da[i][k]*B.da[k][j])%p;

    return C;

}

Matrixnode Pow (Matrixnode A,int x)

{

    Matrixnode re;

    for (int i=; i<m; i++) re.da[i][i]=;

    for (int i=x; i; i>>=,A=Mul(A,A))

        if (i&) re=Mul(re,A);

    return re;

}

void KMP_prework()

{

    for (int j=,i=; i<=m; i++)

        {

            while (j && S[i]!=S[j+]) j=next[j];

            if (S[j+]==S[i]) j++; next[i]=j;

        }

    for (int i=; i<m; i++)

        for (int x,j=; j<; j++)

            {

                x=i;

                while (x && S[x+]-''!=j) x=next[x];

                if (j==S[x+]-'') a.da[i][x+]++; else a.da[i][]++;

            }

}

int main()

{

    scanf("%d%d%d\n",&n,&m,&p); scanf("%s",S+);

    KMP_prework();

    Matrixnode ans; ans=Pow(a,n);

    for (int i=; i<m; i++) an=(an+ans.da[][i])%p;

    printf("%d\n",an);

    return ;

}