Median Replace

Taichi thinks a binary string X of odd length N is beautiful if it is possible to apply the following operation \frac{N-1}{2} times so that the only character of the resulting string is 1 :

• Choose three consecutive bits of X and replace them by their median. For example, we can turn 00110 into 010 by applying the operation to the middle three bits.

Taichi has a string S consisting of characters 0, 1 and ?. Taichi wants to know the number of ways to replace the question marks with 1 or 0 so that the resulting string is beautiful, modulo 10^{9} + 7.

Constraints

• 1 \leq |S| \leq 300000
• |S| is odd.
• All characters of S are either 0, 1 or ?.

Input

Input is given from Standard Input in the following format:

S

Output

Print the number of ways to replace the question marks so that the resulting string is beautiful, modulo 10^{9} + 7.

Examples

Input

1??00

Output

2

Input

?

Output

1

Input

?0101???10???00?1???????????????0????????????1????0

Output

402589311

inputFormat

Input

Input is given from Standard Input in the following format:

S

outputFormat

Output

Print the number of ways to replace the question marks so that the resulting string is beautiful, modulo 10^{9} + 7.

Examples

Input

1??00

Output

2

Input

?

Output

1

Input

?0101???10???00?1???????????????0????????????1????0

Output

402589311

样例

1??00

2