题目描述

阿申准备报名参加GT考试，准考证号为n位数$X_1X_2 \cdots X_n(0 \leq X_i \leq 9)$，他不希望准考证号上出现不吉利的数字。 他的不吉利数字$A_1A_2 \cdot sA_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

备注

对于全部数据，$1 \leq n \leq 10^9,1 \leq m \leq 20,2 \leq K \leq 1000$。