#8952. 「THUPC 2025 初赛」 乒乓球赛 普及+/提高

Menji 喜欢看乒乓球比赛，但由于观赛的人太多，他只能听到一部分的信息。

乒乓球赛一共包含 局，一局乒乓球的过程如下：

两位选手分别有得分，用 和 表示，初始 。

接下来会进行若干个回合，在第 个回合，会有一个获胜者 ，若 则 的得分 ，即 ，否则 的得分 ，即 。当任意一名选手达到 分，且领先另一名选手至少 分时（即 , ），该局立刻结束。

对于每一局比赛，Menji 听到了最终该局进行的回合数 ，以及一部分时刻结束时的比分，例如 Menji 可能在第 回合结束时听到比分是 ，但 Menji 并不知道哪一名选手获得了 分，只知道其中一名选手获得了 分，另外一名选手获得了 分。

具体的，Menji 的信息可以被表示为一个非负整数 ，表示该局恰好进行了 个回合，以及 个长为 的序列 。对于每一个 ，若 ，则 Menji 没有听到任何第 个回合结束时的信息，否则保证 ，表示在第 个回合结束时，一定满足 或 。

显然，很多时候 Menji 的信息并不能还原比赛每一局每一回合的获胜者，甚至有时候 Menji 的信息会是错误的。Menji 想要知道，有多少个获胜者序列 满足他已知的所有信息？

由于答案可能很大，请输出答案对 取模的结果。

第一行一个整数 ，表示乒乓球比赛的局数。

对于每一局：

第一行一个整数 ，表示比赛恰好进行了 回合。

之后 行，每行两个整数 ，满足 或 ，表示 Menji 已知的一部分信息。

保证总回合数不超过 ，即 。

对于每一局，输出一行一个数，表示可能的获胜者序列个数，对 取模。

样例输入 1

复制7
11
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
11
-1 -1
1 1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
11
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
1 11
22
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
11 9
-1 -1
-1 -1
22
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
23
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
22
-1 -1
1 1
-1 -1
3 1
-1 -1
4 2
-1 -1
2 6
-1 -1
-1 -1
5 6
-1 -1
-1 -1
7 7
-1 -1
-1 -1
9 8
-1 -1
9 10
-1 -1
11 10
-1 -1

样例输出 1

复制2
0
0
0
369512
0
864

样例解释

比赛总共进行了 局。

• 对于第一局，恰好进行了 个回合结束，一定是某一选手连胜了 回合，所以获胜者序列一定是全 或是全 ，故答案为 。
• 对于第二局，恰好进行了 个回合结束，但第二回合结束的比分是 ，最终至多只能达到 的比分，因此不存在合法的获胜者序列使得恰好 回合结束，故答案为 。
• 对于第三局，显然不可能在 个回合内达到 的比分，故答案为 。
• 对于第四局，若第 个回合的比分达到 ，则该局会立刻结束，不会进行到第 个回合，故答案为 。
• 对于第五局，双方的得分一定是先达到 ，之后其中一名选手连胜 局，故答案为 。
• 对于第六局，容易发现不可能恰好进行 个回合时结束，故答案为 。
• 对于第七局，我有一个完美的解释，可惜写不下了。

题目来源

题目来自 THUPC2025（2025年清华大学学生程序设计竞赛暨高校邀请赛）初赛，信息来源于 THUSAAC 仓库。