You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

原题来自：HNOI 2008

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

他的不吉利数字 $A_1A_2\cdots A_m(0\le A_i\le 9)$ 有 $m$ 位，不出现是指 $X_1X_2\cdots X_n$ 中没有恰好一段等于 $A_1A_2\cdots A_m$，$A_1$ 和 $X_1$ 可以为 $0$。

输入格式

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

输出格式

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

样例

4 3 100
111

81

数据范围与提示

对于全部数据，$1\le n\le 10^9,1\le m\le 20,2\le K\le 1000$。