4431: Absolute Difference Equation

For a sequence a₁, a₂, …, a_n, consider the following operation f : f(a) = {b₁, b₂, …, b_n-1}, where b_i = |a_i − a_i+1|.

After applying the operation f for n − 1 times, denoted by f ⁿ⁻¹(a), the sequence will become a single element.

Bobo has a sequence a of length n filled with 0, 1 and ?. He would like to know the number of ways modulo (10⁹ + 7) to replace ? to 0 or 1 such that f ⁿ⁻¹(a) = {1}.

The input consists of several test cases terminated by end-of-file. For each test case:

The first line contains a nonempty string a consisting only of 0, 1 and ?, denoting the given sequence.

• 1 ≤ |a| ≤ 10⁶
• The sum of |a| does not exceed 10⁷.

1
?????
1010?1?0

1
16
2