说明

为了庆祝祖国生日，小Z学起了斐波那契数列。

F[0]=0

F[1]=1

F[i]=F[i-2]+F[i-1]

小Z突发奇想，要是这个F是一个string类型该多有趣。

S[0]=”0”

S[1]=”1”

S[i]=S[i-2]S[i-1] (表示连接两个字符串)。

小Z经过科学的计算后发现S[N]会很长很长，但是他只想知道一个问题的答案，就是小Z心中的0/1串T在S[N]中出现了多少次。

这次模P。

输入格式

输入文件string.in。

第一行三个整数N,M,P，N如题中所述、M为串T的长度、P为需要取模的数。

第二行为一个长度为M的0/1串。

输出格式

输出文件string.out。

仅包含一个整数，为出现次数模P之后的值。

7 3 100
101

8

提示

对于30%的数据，满足N<=20；

对于60%的数据，满足N<=10^5,M<=200；

对于100%的数据，满足N<=10^9 ,M<=10000,P<=10^9；

来源

洛谷