Fall with Soldiers

Problem Description

Fall is playing a game about a war. There are $n$ soldiers standing in a line. Some of them belong to the player, while others belong to the enemy. Due to the spies, the belonging of some of them is unknown. Now, as an artillery, the player may win this game under the following rules after identifying the belonging of each soldier: Step 1: Choose a soldier which belongs to the player. There should be exactly two soldiers next to the chosen one, which means the chosen soldier should be neither at the beginning nor at the end of the line. Step 2: Kill the soldiers next to the chosen one (the chosen one will remain alive). Step 3: Repeat step 1 and step 2 until all the soldiers left belong to the same side (the player or the enemy). The player wins if all the soldiers left belong to the player. Fall, as the player, wants to know the number of ways to identify the belonging of each soldier so that he can win. However, soldiers may change their state (the player's troops, the enemies, or unknown). You need to calculate the answers after every change.

Input

The input consists of multiple test cases. The first line contains an integer $T$ ($1 \leq T \leq 11$) -- the number of test cases. For each test case: In the first line, there are two integer $n,q$ ($1 \leq n,q \leq 2 \times 10^5$, $n$ is odd ), which are the number of soldiers and the number of operations. In the second line, there is a string $s$ of length $n$, which represents the initial soldier state. If $s_i$ is '1', the soldier belongs to you. If $s_i$ is '0', the soldier belongs to your enemy. If $s_i$ is '?', the belonging of this soldier is unknown. In the next $q$ lines, each contains an integer $p$ ($1 \leq p \leq |s|$) and a charactor $c$, which means change $s_p$ to $c$. It is guaranteed that the sum of $q$ over all test cases will not exceed $10^6$, $s_i,c \in \{'0','1','?'\}$

Output

For each test case, output the initial answer in a single line. Then output $q$ answers in $q$ lines, which are your answers after each change. All the answers should be output modulo $10^9+7$.

Sample Input

6

5 1

01000

1 1

5 1

00000

3 1

15 4

1100????????111

8 ?

1 0

4 1

11 ?

15 4

0????000?0???0?

6 0

10 0

1 ?

10 ?

15 2

???????0?0???0?

4 0

1 0

15 2

00000000?0???0?

4 ?

4 ?

Sample Output

0

0

0

1

247

247

247

253

253

368

368

368

736

1664

3616

1760

880

0

24

24

Source

2021“MINIEYE杯”中国大学生算法设计超级联赛（7）