题目描述

阿申准备报名参加GT考试，准考证号为n位数$X_1X_2 \cdots X_n(0 \leq X_i \leq 9)$，他不希望准考证号上出现不吉利的数字。 他的不吉利数字$A_1A_2 \cdots A_m(0 \leq A_i \leq 9)$有m位，不出现是指$X_1X_2 \cdots X_n$中没有恰好一段等于$A_1A_2 \cdots A_m$，$A_1$和$X_1$可以为0。

输入描述

第一行输入n,m,K，接下来一行输入m位的数。

输出描述

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

示例1

4 3 100
111

81

备注

数据范围

对于全部数据，$n\leq10^9$，$m\leq 20$，$K\leq10000$。