#412. [HNOI2008] GT考试

[HNOI2008] GT考试

题目描述

原题来自:HNOI 2008

阿申准备报名参加 GT 考试,准考证号为 nn 位数 X1X2Xn(0Xi9)X_1X_2\cdots X_n(0\le X_i\le 9),他不希望准考证号上出现不吉利的数字。

他的不吉利数字 A1A2Am(0Ai9)A_1A_2\cdots A_m(0\le A_i\le 9)mm 位,不出现是指 X1X2XnX_1X_2\cdots X_n 中没有恰好一段等于 A1A2AmA_1A_2\cdots A_mA1A_1X1X_1 可以为 00

输入格式

第一行输入 n,m,Kn,m,K,接下来一行输入 mm 位的数。

输出格式

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

样例

4 3 100
111
81

数据范围与提示

对于全部数据,1n109,1m20,2K10001\le n\le 10^9,1\le m\le 20,2\le K\le 1000