#P18196. 0100 Insertion
0100 Insertion
0100 Insertion
从一个空字符串 开始,可以反复执行以下操作:
- 在 的任意位置插入字符串
0100。
能够通过上述操作得到的字符串称为好字符串。
给定长度为 、仅由 0、1 和 ? 组成的字符串 。将其中每个 ? 替换为 0 或 1,求能够得到多少个不同的好字符串。答案对 取模。
计算的是不同的最终字符串;同一个字符串即使有多种插入过程,也只计算一次。
输入格式
N
S
输入满足:
- ;
- 是 的倍数;
- 的长度为 ,仅含字符
0、1和?。
输入只有一组数据。
输出格式
输出一个整数,表示答案模 的值。
样例 1
输入
8
0??0?100
输出
2
说明
满足条件的好字符串是 00100100 和 01000100。
样例 2
输入
4
?10?
输出
1
样例 3
输入
28
???????????0???0??????1???0?
输出
2023