Background

Original problem link: https://oier.team/problems/S7D.

Problem Description

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$.

Input Format

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}$.

Output Format

For each test case:

• Output a single line with one integer, the answer modulo $10^9 + 7$.

5
3 0
5 2
2 0
4 1
6 3
1 0
2 1
4 1
1234 4
52 1
110 1
520 0
999 1
114514 0

3
12
32
27109943
596672839

Hint

[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\}$.

• 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