Problem A
0-1 Sequences
You are given a sequence, in the form of a string with characters ‘0’, ‘1’, and ‘?’ only. Suppose there are $k$ ‘?’s. Then there are $2^ k$ ways to replace each ‘?’ by a ‘0’ or a ‘1’, giving $2^ k$ 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 $5$ inversions. We can sort it by the following moves: 11010 $\rightarrow $ 11001 $\rightarrow $ 10101 $\rightarrow $ 01101 $\rightarrow $ 01011 $\rightarrow $ 00111.
Find the sum of the number of inversions of the $2^ k$ sequences, modulo $1\, 000\, 000\, 007$ ($10^9 + 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 $1$ to $500\, 000$ characters, inclusive.
Output
Output an integer indicating the aforementioned number of inversions modulo $1\, 000\, 000\, 007$.
Sample Input 1 | Sample Output 1 |
---|---|
?0? |
3 |