题目描述

阿申准备报名参加 $GT$ 考试，准考证号为 $n$ 位数 $X_1X_2....X_n$，他不希望准考证号上出现不吉利的数字。

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

输入

第一行输入 $n,m,K$。

接下来一行输入 $m$位的不吉利数字。

输出

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

4 3 100 
111

81

提示

$0 \leq X_i,A_i \leq 9$

$1 \leq n \leq 10^9$

$1 \leq m \leq 20$

$2 \leq K \leq 1000$