[HNOI2008]GT考试

阿申准备报名参加 GT 考试，他的准考证号是一个长度为 $N$ 的数字串 $X_1X_2\cdots X_N$，其中 $0\le X_i\le 9$，且 $X_1$ 可以为 $0$。

阿申有一个长度为 $M$ 的不吉利数字串 $A_1A_2\cdots A_M$，其中 $0\le A_i\le 9$，且 $A_1$ 可以为 $0$。他不希望准考证号中出现一段连续的子串，恰好等于这个不吉利数字串。

请计算有多少种长度为 $N$ 的准考证号不包含该不吉利数字串。

输入格式

第一行输入三个整数 $N,M,K$。

第二行输入一个长度为 $M$ 的数字串，表示不吉利数字串。该数字串可能包含前导零。

输出格式

输出一个整数，表示合法准考证号的数量对 $K$ 取模后的结果。

样例输入

4 3 100
111

样例输出

81

数据范围

• $N\le 10^9$，$M\le 20$；
• $1\le K\le 10^4$；
• $0\le X_i\le 9$，$0\le A_i\le 9$。

来源与许可

本题为 HNOI 2008 试题「GT考试」，题面与测试数据整理自 BZOJ。

样例 1

输入

4 3 100
111

输出

81