For a sequence a1, a2, ... , an, consider the following operation f: f(a) = {b1, b2, ... , bn-1}, where bi = |ai - ai+1|.
After applying the operation f for n - 1 times, denoted by fn-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 (109+7) to replace ? to 0 or 1 such that fn-1(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 0, 1, and ?, denoting the giving sequence.
· 1 ≤ |a| ≤ 106
· The sum of |a| does not exceed 107
输出描述:
For each test case, print an integer which denotes the result.