408225: GYM103059 F Famished Flesheating Frogs

Alice and Bob have been abducted by an alien race of flesheating frogs! The frogs often get bored and like to play with their food. Their favorite method is a game called "1-D Leapfrog".

1-D Leapfrog is a game performed on an one dimensional board of $$$N$$$ boxes, indexed by consecutive integers from $$$0$$$ to $$$N-1$$$, inclusive. Each box contains at most 1 frog.

Each frog on the board can "leap" from one box to another. In one leap, a frog in box $$$i$$$ can leap to any box $$$0 \leq j < i$$$, such that all the intermediate boxes $$$k$$$ ($$$i > k > j$$$) have frogs in them, and $$$j$$$ currently is empty. It is possible that there are no intermediate boxes that are jumped over in a single leap.

The board is initialized with some number of frogs. Alice and Bob take turns commanding frogs to leap, with Alice going first. When a player doesn't give a command, cannot give a command, or gives an invalid command, the frogs get very irritated and consume the offending player, bones and all.

Bob realizes he is at a disadvantage with this game, and proposes a new variant, called 2-D Leapfrog. 2-D Leapfrog consists of playing $$$M$$$ games of 1-D Leapfrog simultaneously. Play proceeds as follows:

• Alice chooses one of the games of 1-D Leapfrog
• Alice then makes a valid leap in the selected game
• If Alice cannot make a valid leap, then Alice is eaten alive
• Bob chooses one of the games of 1-D Leapfrog
• Bob then makes a valid leap in the selected game
• If Bob cannot make a valid leap, then Bob is eaten alive
• Repeat

Alice and the frogs are fascinated with this new game, and want to play immediately! They have gathered $$$M$$$ 1-D Leapfrog boards. However, Bob has gotten suspicious that Alice has rigged the game against him, and decides to randomize the direction of the 1-D boards before play begins. That is, before the game starts, for each board independently with probability $$$\frac{1}{2}$$$, he reverses the board.

Assuming that Alice and Bob both play optimally on the potentially modified set of boards, what is the probability that Bob survives?

The first line of input contains a single integer $$$M$$$ ($$$1 \leq M \leq 5 \cdot 10^6$$$) representing the number of 1-D boards, followed by $$$M$$$ lines of the following form:

A single positive integer $$$N$$$, the length of the board, followed by a string $$$s$$$ consisting of $$$N$$$ characters that are either 0 or 1, where the $$$i$$$-th position is 1 if a frog is at that position and $$$0$$$ otherwise.

The sum of the length of the boards is at most $$$5 \cdot 10^6$$$.

If $$$P$$$ is the probability Bob survives, output a single integer $$$(P \cdot 2^M) \mod (10^9 + 7)$$$.

1
3 010

0

2
2 01
2 10

2