You are given a sequence, in the form of a string with characters ‘0’, ‘1’, and ‘?’ only. Suppose there are kk ‘?’s. Then there are 2k2k ways to replace each ‘?’ by a ‘0’ or a ‘1’, giving 2k2k different 0-1 sequences (0-1 sequences are sequences with only zeroes and ones).

For each 0-1 sequence, define its number of inversions as the minimum number of adjacent swaps required to sort the sequence in non-decreasing order. In this problem, the sequence is sorted in non-decreasing order precisely when all the zeroes occur before all the ones. For example, the sequence 11010 has 55 inversions. We can sort it by the following moves: 11010 →→ 11001 →→ 10101 →→ 01101 →→ 01011 →→ 00111.

Find the sum of the number of inversions of the 2k2k sequences, modulo 10000000071000000007 (109+7109+7).

Input

The first and only line of input contains the input string, consisting of characters ‘0’, ‘1’, and ‘?’ only, and the input string has between 11 to 500000500000 characters, inclusive.

Output

Output an integer indicating the aforementioned number of inversions modulo 10000000071000000007.
sample input ?0?

sample output

3

Answer rating: 100% (QA)

Answer Solution I have atta... View the full answer