AtCoder Grand Contest 022
翻译中…
Problem Statement
翻译中…
Taichi thinks a binary string $X$ of odd length $N$ is beautiful if it is possible to apply the following operation $\frac{N-1}{2}$ times so that the only character of the resulting string is 1 :
翻译中…
- Choose three consecutive bits of
$X$and replace them by their median. For example, we can turn00110into010by applying the operation to the middle three bits.
翻译中…
Taichi has a string $S$ consisting of characters 0, 1 and ?. Taichi wants to know the number of ways to replace the question marks with 1 or 0 so that the resulting string is beautiful, modulo $10^{9} + 7$.
翻译中…
Constraints
翻译中…
$1 \leq |S| \leq 300000$$|S|$is odd.- All characters of
$S$are either0,1or?.
翻译中…
Input
翻译中…
Input is given from Standard Input in the following format:
翻译中…
S翻译中…
Output
翻译中…
Print the number of ways to replace the question marks so that the resulting string is beautiful, modulo $10^{9} + 7$.
翻译中…
样例
Input #1
1??00
Output #1
2
There are $4$ ways to replace the question marks with `0` or `1` :
- `11100` : This string is beautiful because we can first perform the operation on the last $3$ bits to get `110` and then on the only $3$ bits to get `1`.
- `11000` : This string is beautiful because we can first perform the operation on the last $3$ bits to get `110` and then on the only $3$ bits to get `1`.
- `10100` : This string is not beautiful because there is no sequence of operations such that the final string is `1`.
- `10000` : This string is not beautiful because there is no sequence of operations such that the final string is `1`.
Thus, there are $2$ ways to form a beautiful string.
Input #2
?
Output #2
1
In this case, `1` is the only beautiful string.
Input #3
?0101???10???00?1???????????????0????????????1????0
Output #3
402589311
Remember to output your answer modulo $10^{9} + 7$.
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。