友情提示：380元/半年，儿童学编程，就上码丁实验室。
【题目描述】
小Z学起了斐波那契数列。
$F[0]=0$
$F[1]=1$
$F[i]=F[i-2]+F[i-1]$
小Z突发奇想，要是这个$F$是一个$string$类型该多有趣。
$S[0]=“0”$
$S[1]=“0”$
$S[i]=S[i-2]S[i-1]$ (表示连接$S[i-2]$和$S[i-1]$两个字符串)。
小Z经过科学的计算后发现$S[N]$会很长很长，但是他只想知道一个问题的答案，就是小Z心中的$0/1$串$T$在$S[N]$中出现了多少次。
答案对$P$取模。
【输入】
第一行三个整数$N,M,P$，$N$如题中所述，$M$为串$T$的长度，$P$为需要取模的数。
第二行为一个长度为$M$的$0/1$串。
【输出】
仅包含一个整数，为出现次数模$P$之后的值。
【输入样例】
7 3 100 101
【输出样例】
8
【提示】
【数据规模】
对于30%的数据，$N≤20$。
对于60%的数据，$N≤10^5，M≤200$。
对于100%的数据，$N≤10^9，M≤10000，P≤10^9$。