P11326 [MX-S7-T4] "SMOI-R2" XA-Game.

Original problem link: .

Alice and Bob are playing a game. Initially, there is a 01 sequence of length $n$, with positions numbered $1,2,\dots,n$. The two players take turns operating, and Alice moves first. Alice's move is to choose any two adjacent numbers in the sequence and merge them into their **xor value** (i.e. the `^` operator in C++). Bob's move is to choose any two adjacent numbers in the sequence and merge them into their **and value** (i.e. the `&` operator in C++). The game continues until there is only one number left in the sequence. If the final remaining number is $1$, Alice wins; otherwise, Bob wins. Before the game starts, Bob casts $m$ spells to adjust the initial sequence. The $i$-th spell changes the number at position $a_i$ to $v_i$. Alice wants to know: if both players use optimal strategies, how many possible **initial sequences** (before Bob casts his spells) can allow her to win the game. Since the answer may be very large, you need to output it modulo the prime $10^9 + 7$.

**This problem contains multiple test cases.** The first line contains a positive integer $T$, the number of test cases. Then for each test case: - The first line contains two non-negative integers $n, m$, representing the length of the 01 sequence and the number of Bob's spell operations. - The next $m$ lines: the $i$-th line contains two non-negative integers $a_i, v_i$, meaning that the $i$-th spell changes the number at position $a_i$ to $v_i$. **It is guaranteed that $\boldsymbol{a_i}$ are given in strictly increasing order, i.e. $\boldsymbol{1 \le a_1 < a_2 < \cdots < a_m \le n}$.**

For each test case: - Output a single line with one integer, the answer modulo $10^9 + 7$.

**[Sample Explanation #1]** In the first test case, the sequences that allow Alice to win are $110$, $101$, and $011$, for a total of $3$. In the second test case, the sequences that allow Alice to win are $10100$, $11100$, $10110$, $11110$, $10001$, $11001$, $00101$, $01101$, $10011$, $11011$, $00111$, and $01111$, for a total of $12$. For the sequence $11100$, after Bob finishes casting spells it becomes $10110$. Alice's first move can merge the fourth and fifth numbers, making the sequence become $1011$. It can be seen that no matter how Bob plays, Alice will win. **[Sample #2]** See `game/game2.in` and `game/game2.ans` in the attachments. This sample satisfies the constraints of test points $5\sim6$. **[Sample #3]** See `game/game3.in` and `game/game3.ans` in the attachments. This sample satisfies the constraints of test points $10\sim11$. **[Sample #4]** See `game/game4.in` and `game/game4.ans` in the attachments. This sample satisfies the constraints of test points $12\sim13$. **[Sample #5]** See `game/game5.in` and `game/game5.ans` in the attachments. This sample satisfies the constraints of test points $18\sim20$. **[Constraints]** For all testdata, it is guaranteed that: $1\le T\le5\times 10^5$, $1\le n\le 10^{15}$, $0\le m\le n$, $\sum m \le5\times 10^5$, $1\le a_i\le n$, $a_i < a_{i + 1}$, $v_i\in\{0,1\}$. |Test Point ID|$T\le$|$n\le$|$\sum m\le$|Special Property| |:-:|:-:|:-:|:-:|:-:| |$1$|$40$|$20$|$40$|None| |$2\sim4$|$10^3$|$5\times10^2$|$5\times10^5$|A| |$5\sim6$|$10^3$|$5\times10^2$|$5\times10^5$|B| |$7\sim9$|$10^3$|$5\times10^2$|$5\times10^5$|C| |$10\sim11$|$2\times 10^5$|$10^6$|$0$|None| |$12\sim13$|$2\times 10^5$|$10^6$|$2\times10^5$|None| |$14$|$2\times 10^3$|$10^{15}$|$0$|None| |$15\sim16$|$2\times 10^3$|$10^{15}$|$2\times10^3$|None| |$17$|$5\times 10^5$|$10^{15}$|$0$|None| |$18\sim20$|$5\times 10^5$|$10^{15}$|$5\times10^5$|None| - Special property A: $n = m$. - Special property B: $n = m$, and $v_i=1$. - Special property C: $n = m$, and there are no two adjacent $0$ in $v$, i.e. $v_i + v_{i + 1} \ne 0$. Translated by ChatGPT 5