QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 1024 MB
[0]

# 3763. Absolute Difference Equation

Statistics

For a sequence a1,a2,,an, consider the following operation f: f(a)={b1,b2,,bn1}, where bi=|aiai+1|.

After applying the operation f for n1 times, denoted by fn1(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 (109+7) to replace ? to 0 or 1 such that fn1(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|106
  • The sum of |a| does not exceed 107.

Output

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

Sample Input

1
?????
1010?1?0

Sample Output

1
16
2