题目描述

S0="0"，S1="1"，Si=Si−2 Si−1表示字符串拼接。给定N和01模式T，求T在SN中出现次数模P，允许重叠。

本题为一本通1796的公开本地训练修订版。

输入

第一行N M P，0≤N≤10^9，1≤M≤10000，1≤P≤10^9；下一行长度M的01串T。

输出

输出一个0..P−1的整数。

输入样例

7 3 100
101

输出样例

8

修订说明

把原S1="0"公开纠正为"1"；若两初值全0则样例模式101永不出现，与输出8矛盾。保留全N/M/P范围，明确重叠和N0。

本地修订与来源

本题为经授权补全的本地训练修订版，原始公开题面保留在采集档案；修订了：把原S1="0"公开纠正为"1"；若两初值全0则样例模式101永不出现，与输出8矛盾。保留全N/M/P范围，明确重叠和N0。。此处题意、范围和输出约定以本修订版为准，不冒称原站或官方原版。原题链接：https://ybt.ssoier.cn/problem_show.php?pid=1796。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共6个测试点，非原站或官方原始数据。总分100分。