Description

Original source: HNOI 2008

Ashen is preparing to register for the GT exam. The admission ticket number is an $n$-digit number $X_1X_2\cdots X_n(0\le X_i\le 9)$. He does not want any unlucky digits to appear on his ticket number.

His unlucky number is an $m$-digit number $A_1A_2\cdots A_m(0\le A_i\le 9)$. The ticket number is considered unlucky if it contains any contiguous subsequence exactly equal to $A_1A_2\cdots A_m$. Note that $A_1$ and $X_1$ can be $0$.

Input Format

The first line contains three integers $n,m,K$. The next line contains the $m$-digit unlucky number.

Output Format

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

Sample 1

4 3 100
111

81

Data Range and Hint

For all data, $1\le n\le 10^9,1\le m\le 20,2\le K\le 1000$.