博弈

Problem Description

Alice 和 Bob 又要玩取石子游戏了。有 $n$ 个房间，第 $i$ 个房间中有 $k_i$ 堆石子（$k_i \geq 1$）。Alice 和 Bob 轮流进行操作，Alice 先手。每次操作时，玩家可以在任何一个房间中选择任何一个非空的堆，然后从该堆中取出任意个石子。若某位玩家无法进行操作（即所有房间都是空的），则该玩家输掉游戏。 为了增加游戏的乐趣，他们新加了一个规则：在当前房间内还有石子时，不允许到其他房间内取石子。且游戏开始前给定一个长度为 $n$ 的排列 $p$，表示访问顺序。当 $p_i$ 房间内没有石子的情况下， 才可以去 $p_{i + 1}$ 房间内取石子。注意，在游戏开始前，两人都知道这个排列。 在游戏开始前，Alice 可以决定房间的访问顺序。假设 Alice 和 Bob 都是最聪明的。Alice 想知道有多少种排列能使她获胜。 由于结果可能非常大，请输出答案对 $10^9 + 7$ 取模。

Input

第一行输入一个整数 $T$ （$1 \le T \le 100$），表示测试的总数。 对于每个测试用例，第一行输入一个整数 $n$（$1 \le n \le 10^6$），表示房间的总数。 接下来 $n$ 行，每行的开始有一个整数 $k_i$，表示该房间中有多少堆石子。接下来输入 $k_i$ 个整数 $a_1, a_2, \cdots, a_{k_i}$（$1 \leq a \leq 10^9$），表示每堆石子包含的数量。保证所有样例中 $k_i$ 的总和不超过 $10^6$。

Output

对于每个测试，输出一个整数，表示 Alice 获胜的方案数，结果对 $10^9 + 7$ 取模。

Sample Input

2
2
1 1
1 2
4
3 1 2 3
1 1
4 1 2 3 4
5 1 2 3 4 5

Sample Output

1
14

Hint

对于第一个样例，如果房间的顺序是 1 2，那么 Alice 第一步只能取走房间1中唯一的一个石子，然后 Bob 可以把房间2中的石子全部取完，Bob 获胜；如果房间的顺序是 2 1，那么 Alice 可以取走房间2中的一个石子，接下来 Bob 只能取房间2中剩下的一个石子。然后 Alice 取走房间1中剩下的一个石子，最终获胜。因此答案是 1。

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（1）