Touxinzei 终究无法纯净自己的心,只能眼看自己心爱的女子渐行渐远,从此他让琪露诺将自己的心尘封起来了,在他的世界不再有爱,只剩下了0和1......
Touxinzei 对于 和 有着自己的见地, 代表着不爱, 代表着爱,他认为 和 是会相互转换的,即爱与不爱之间是可以互相转换的。
最初,Touxinzei 只有一个二进制数 。设当前这个二进制数为 ,那么在一次操作后,这个二进制数会变为 ,它是由 变化而来的:
我们将最初的二进制数 称为 ,第 个生成出来的二进制数称为 ,那么前几个数如下:
0 | 0 |
1 | 1 |
2 | 10 |
3 | 101 |
4 | 10110 |
5 | 10110101 |
6 | 1011010110110 |
现在给定了一个 串 和一个数字 ,Touxinzei 想知道 在 中出现的次数,输出可能过大,请你将答案对 取模。
输入
输入一行一个整数 ( ) ,含义如题目所示。
接下来输入一行一个只包含 和 的字符串 ,长度不超过 。
输出
输出一行一个整数表示答案。
样例
标准输入 复制文本 |
0 1 |
标准输出 复制文本 |
0 |
标准输入 复制文本 |
6 10 |
标准输出 复制文本 |
5 |
标准输入 复制文本 |
6 101 |
标准输出 复制文本 |
4 |