有 $n$ 个房间，第 $i$ 个房间中有 $k_i$ 堆石子（$k_i\ge 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\le a\le 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

Output

1
14

Hint

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