题目描述

Alice 和 Bob 在玩一个游戏。

初始地，有一个长度为 $n$ 的 01 序列，位置编号为 $1,2,\dots,n$。双方轮流操作，Alice 先操作。

Alice 的操作是任意选择序列中位置相邻的两个数，将它们合并为它们的异或值（即 C++ 中的 ^ 操作）。

Bob 的操作是任意选择序列中位置相邻的两个数，将它们合并为它们的与值（即 C++ 中的 & 操作）。

游戏将持续进行，直至序列中仅剩一个数。如果最后剩下的数是 $1$，Alice 获胜；否则，Bob 获胜。

在游戏开始前，Bob 施展了 $m$ 次魔法调整初始序列，第 $i$ 次魔法将第 $a_i$ 个位置的数改为 $v_i$。

Alice 想知道，如果双方都使用最优策略，有多少种可能的初始序列（在 Bob 施展魔法之前）能够让她赢得游戏。由于答案可能非常大，你需要将结果对质数 $10^9 + 7$ 取模。

输入格式

本题有多组测试数据。

第一行，一个正整数 $T$，表示数据组数。接下来，对于每组数据：

• 第一行，两个非负整数 $n, m$，分别表示 01 序列的长度和 Bob 的魔法操作次数。
• 接下来 $m$ 行，第 $i$ 行两个非负整数 $a_i, v_i$，表示第 $i$ 次魔法操作将第 $a_i$ 个位置的数改为 $v_i$。保证 $\boldsymbol{a_i}$ 严格递增给出，即 $\boldsymbol{1 \le a_1 < a_2 < \cdots < a_m \le n}$。

输出格式

对于每组测试数据：

• 仅一行，一个整数，表示答案对 $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

样例 1 解释

第一组数据中，可以让 Alice 赢的序列有 $110$、$101$、$011$ 共 $3$ 种。

第二组数据中，可以让 Alice 赢的序列有 $10100$、$11100$、$10110$、$11110$、$10001$、$11001$、$00101$、$01101$、$10011$、$11011$、$00111$、$01111$ 共 $12$ 种。

其中序列 $11100$，在 Bob 实施完魔法后变成了 $10110$。Alice 第一次操作可以合并第四个数和第五个数，序列变成 $1011$，可以发现 Bob 无论怎么操作 Alice 都会赢。

样例 2

见附件中的 game/game2.in 与 game/game2.ans。

该组样例满足测试点 $5\sim6$ 的约束条件。

样例 3

见附件中的 game/game3.in 与 game/game3.ans。

该组样例满足测试点 $10\sim11$ 的约束条件。

样例 4

见附件中的 game/game4.in 与 game/game4.ans。

该组样例满足测试点 $12\sim13$ 的约束条件。

样例 5

见附件中的 game/game5.in 与 game/game5.ans。

该组样例满足测试点 $18\sim20$ 的约束条件。

数据范围

对于所有测试数据，保证：$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\}$。

测试点编号	$T\le$	$n\le$	$\sum m\le$	特殊性质
$1$	$40$	$20$	$40$	无
$2\sim4$	$10^3$	$5\times10^2$	$5\times10^5$	A
$5\sim6$				B
$7\sim9$				C
$10\sim11$	$2\times 10^5$	$10^6$	$0$	无
$12\sim13$			$2\times10^5$
$14$	$2\times 10^3$	$10^{15}$	$0$
$15\sim16$			$2\times10^3$
$17$	$5\times 10^5$		$0$
$18\sim20$			$5\times10^5$

• 特殊性质 A：$n = m$。
• 特殊性质 B：$n = m$，且 $v_i=1$。
• 特殊性质 C：$n = m$，且 $v$ 中没有相邻的两个 $0$，即 $v_i + v_{i + 1} \ne 0$。

下发文件

通过点击此链接下载下发文件。