设f[i,j]为准考证号上第i位匹配到不吉祥数字第j位的方案数,显然j∈[0,m-1]
下面我们就要想到怎么把f[i-1]转移到f[i]
也就是当前匹配到第k位，那么下一位可能会匹配到哪一位
显然我们可以穷举下一位的字符，利用KMP求出下一位会匹配到哪一位（KMP的失配思想）
然后可以得出f[i,j]=f[i-1,0]*w[0,j]+f[i-1,1]*w[1,j]……+f[i-1,m-1]*w[m-1,j]
w[x,y]表示下一位取值能使由上一位匹配到y转移到下一位配到x的数目
然后就是矩乘+快速幂了（感觉解释的很不清楚……）
var a,b,c,w:array[..,..] of longint;
next,d:array[..] of longint;
n,m,p,i,j,k,ans:longint;
s:ansistring;
ch:char; procedure mul;
var i,j,k:longint;
begin
for i:= to m- do
for j:= to m- do
begin
c[i,j]:=;
for k:= to m- do
c[i,j]:=(c[i,j]+a[i,k]*b[k,j] mod p) mod p;
end;
end; begin
readln(n,m,p);
readln(s);
for i:= to m do
begin
while (j<>) and (s[i]<>s[j+]) do j:=next[j];
if s[i]=s[j+] then
begin
inc(j);
next[i]:=j;
end;
end;
for i:= to m- do
for j:= to do
begin
ch:=chr(j+);
k:=i;
while (k<>) and (s[k+]<>ch) do k:=next[k];
if s[k+]=ch then inc(k);
inc(w[k,i]);
end; for i:= to m- do
c[i,i]:=;
j:=;
while n> do
begin
inc(j);
d[j]:=n mod ;
n:=n shr ;
end;
for i:=j downto do
begin
a:=c;
b:=c;
mul;
if d[i]= then
begin
a:=c;
b:=w;
mul;
end;
end;
for i:= to m- do
ans:=(ans+c[i,]) mod p;
writeln(ans);
end.