题目描述

原题来自：HNOI 2008

阿申准备报名参加$\red{ GT }$考试，准考证号为$\red n$ 位数 $\red{X_1X_2\cdots X_n(0\le X_i\le 9)}$，他不希望准考证号上出现不吉利的数字。

他的不吉利数字$\red{ A_1A_2\cdots A_m(0\le A_i\le 9) }$有$\red{ m }$位，不出现是指$\red{ X_1X_2\cdots X_n }$中没有恰好一段等于$\red{ A_1A_2\cdots A_m}$​，$\red{A_1 }$和$\red{ X_1}$ 可以为$\red{ 0}$。

输入格式

第一行输入$\red{ n,m,K}$，接下来一行输入$\red m$ 位的数。

输出格式

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

样例

输入样例

4 3 100
111

输出样例

81

数据范围与提示

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