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