Problem1705--GT 考试

1705: GT 考试

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 3  Solved: 3
[Submit] [Status] [Web Board] [Creator:]

Description

阿申准备报名参加 GT 考试,准考证号为 n 位数 X1X2....Xn (0 ≤ Xi ≤ 9),他不希望准考证号上出现不吉利的数字。

他的不吉利数字 A1A2....Am (0 ≤ Ai ≤ 9) 有 m 位,不出现是指 X1X2....Xn 中没有恰好一段等于A1A2....Am,A1 和 X1 可以为 0 。

Input

第一行输入 n,m,k,接下来一行输入 m 位的数。

Output

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

Sample Input Copy

4 3 100 
111

Sample Output Copy

81

HINT

对于全部数据,1 ≤ n ≤10^9 , 1 ≤ m ≤ 20, 2 ≤ ≤ 1000

Source/Category