Ashen is preparing to register for the GT exam. His 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 numbers to appear on his ticket. Ashen's unlucky number $a_1a_2\cdots a_m$ ($0\le a_i\le 9$) has $m$ digits. "Not appearing" means that the sequence $x_1x_2\cdots x_n$ does not contain $a_1a_2\cdots a_m$ as a contiguous substring. Both $x_i$ and $a_i$ can be $0$.

Ashen wants to know how many such admission ticket numbers exist that do not contain the unlucky number. Since this number might be very large, you only need to output the remainder when this count is divided by $K$.

Input

The first line contains three integers separated by spaces: $n$, $m$, and $K$. The next line contains a digit string $a_1a_2\cdots a_m$, representing the unlucky number of length $m$.

For $100\%$ of the input data: $n\le 10^9$, $m\le 20$, $K\le 1000$. For $40\%$ of the input data: $n\le 1000$. For $10\%$ of the input data: $n\le 6$.

Output

Output a single integer representing the number of valid admission ticket numbers modulo $K$.

Examples

Input 1

4 3 100
111

Output 1

81

Input 2

3 0 100

Output 2

0