题目描述

阿申准备报名参加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$。$x_i,a_i$ 均可为 $0$。

现在阿申想知道不出现不吉利数字的准考证号有多少种？不过聪明的你很快就发现这个数可能会很大，所以你只要告诉他这个数除 $K$ 之后的余数即可。

输入格式

第 $1$ 行是彼此用一个空格隔开的 $3$ 个整数，分别是 $n,m$ 和 $K$。接下来的 $1$ 行是一个数字串 $a_1a_2\cdots a_m$，代表一个长度为 $m$ 的不吉利数字。

其中，$100%$ 的输入数据满足：$n\le 10^9$，$m\le 20$，$K\le 1000$。$40%$ 的输入数据满足：$n\le 1000$。$10%$ 的输入数据满足：$n\le 6$。

输出格式

仅包含一个整数，表示不出现不吉利数字的准考证号的种数除 $K$ 之后的余数。

样例数据

输入输出样例1

input.txt

4 3 100
111

output.txt

81

输入输出样例2

input.txt

3 0 100

output.txt

0