atcoder#AGC022E. [AGC022E] Median Replace
[AGC022E] Median Replace
Score : points
Problem Statement
Taichi thinks a binary string of odd length is beautiful if it is possible to apply the following operation times so that the only character of the resulting string is 1
:
- Choose three consecutive bits of and replace them by their median. For example, we can turn
00110
into010
by applying the operation to the middle three bits.
Taichi has a string 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 .
Constraints
- is odd.
- All characters of are either
0
,1
or?
.
Input
Input is given from Standard Input in the following format:
Output
Print the number of ways to replace the question marks so that the resulting string is beautiful, modulo .
1??00
2
There are 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 bits to get110
and then on the only bits to get1
.11000
: This string is beautiful because we can first perform the operation on the last bits to get110
and then on the only bits to get1
.10100
: This string is not beautiful because there is no sequence of operations such that the final string is1
.10000
: This string is not beautiful because there is no sequence of operations such that the final string is1
.
Thus, there are ways to form a beautiful string.
?
1
In this case, 1
is the only beautiful string.
?0101???10???00?1???????????????0????????????1????0
402589311
Remember to output your answer modulo .