题目描述
原题来自：HNOI 2008
阿申准备报名参加 GT 考试，准考证号为
n
n 位数
X_1X_2\cdots X_n(0\le X_i\le 9)
X1
X2
⋯Xn
(0≤Xi
≤9)，他不希望准考证号上出现不吉利的数字。
他的不吉利数字
A_1A_2\cdots A_m(0\le A_i\le 9)
A1
A2
⋯Am
(0≤Ai
≤9) 有
m
m 位，不出现是指
X_1X_2\cdots X_n
X1
X2
⋯Xn
中没有恰好一段等于
A_1A_2\cdots A_m
A1
A2
⋯Am
，
A_1
A1
和
X_1
X1
可以为
0
0。
输入
第一行输入
n,m,K
n,m,K，接下来一行输入
m
m 位的数。
输出
阿申想知道不出现不吉利数字的号码有多少种，输出模
K
K 取余的结果。
样例输入
4 3 100
111
样例输出
81
提示
数据范围与提示
对于全部数据，
1\le n\le 10^9,1\le m\le 20,2\le K\le 1000
1≤n≤109,1≤m≤20,2≤K≤1000。
来源/分类
ybttg 矩阵 KMP DP