斐波那契串 - ROJ

【题目描述】

小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

【输出样例】

【提示】

【数据规模】对于30%的数据， $N≤20$ 。对于60%的数据， $N≤10^5，M≤200$ 。对于100%的数据， $N≤10^9，M≤10000，P≤10^9$ 。