P3193 [HNOI2008] GT Exam

Ashen is preparing to register for the GT Exam. His examinee number is an $N$-digit sequence $X_1,X_2…X_n\ (0\le X_i\le 9)$, and he does not want any unlucky number to appear in it. His unlucky number is an $M$-digit sequence $A_1,A_2,\cdots, A_m\ (0\le A_i\le 9)$. “Does not appear” means that in $X_1,X_2\cdots X_n$ there is no contiguous segment exactly equal to $A_1,A_2,\cdots ,A_m$. Both $A_1$ and $X_1$ may be $0$.

The first line contains $N,M,K$. The next line contains an $M$-digit number.

Ashen wants to know how many examinee numbers do not contain the unlucky number. Output the result modulo $K$.

### Constraints For all testdata, $N\leq10^9$, $M\leq 20$, $K\leq10000$. Translated by ChatGPT 5