1092 : Absolute Difference Equation

Description

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^n − 1(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^n − 1(a) = {1}.

Input

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⁷.

Output

For each test case, print an integer which denotes the result.

Sample

1
?????
1010?1?0

1
16
2

Hint

Source

Author

ftiasch