P11326 【MX-S7-T4】「SMOI-R2」XA-Game

原题链接：。

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$ 取模。

无

无

**【样例解释 #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$|$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$|无| |$12\sim13$|$2\times 10^5$|$10^6$|$2\times10^5$|无| |$14$|$2\times 10^3$|$10^{15}$|$0$|无| |$15\sim16$|$2\times 10^3$|$10^{15}$|$2\times10^3$|无| |$17$|$5\times 10^5$|$10^{15}$|$0$|无| |$18\sim20$|$5\times 10^5$|$10^{15}$|$5\times10^5$|无| - 特殊性质 A：$n = m$。 - 特殊性质 B：$n = m$，且 $v_i=1$。 - 特殊性质 C：$n = m$，且 $v$ 中没有相邻的两个 $0$，即 $v_i + v_{i + 1} \ne 0$。