题目描述

钓鱼游戏是一种使用一副卡牌进行的游戏，这副卡牌包含 $3N$ 对卡牌，编号 $1\sim 3N$（一副卡牌中有 $6N$ 张牌）。

三位朋友（$\text{A}$、$\text{B}$ 和 $\text{C}$）参与钓鱼游戏。游戏过程如下：

1. 发牌：每位玩家首先获得 $2N$ 张卡牌。
2. 弃牌：每位玩家丢弃手中所有相同数值的卡牌对。
3. 打牌：重复以下三个步骤，直至所有剩余卡牌被丢弃：
   • $\text{A}$ 将自己的一张卡牌传给 $\text{B}$（除非 $\text{A}$ 没有剩余卡牌）。若此时 $\text{B}$ 拥有相同数值的卡牌对，则立即丢弃这对卡牌。
   • $\text{B}$ 将自己的一张卡牌传给 $\text{C}$（除非 $\text{B}$ 没有剩余卡牌）。若此时 $\text{C}$ 拥有相同数值的卡牌对，则立即丢弃这对卡牌。
   • $\text{C}$ 将自己的一张卡牌传给 $\text{A}$（除非 $\text{C}$ 没有剩余卡牌）。若此时 $\text{A}$ 拥有相同数值的卡牌对，则立即丢弃这对卡牌。

已知在「打牌」阶段的每轮循环中至少有一对相同数值的卡牌被丢弃。

给定三位玩家在「发牌」阶段结束后的手牌状态，请计算不同的游戏过程数量。由于结果可能很大，只需要算出答案对 $(10^9+7)$ 取模的结果。

定义：两种游戏过程被视为不同的，当且仅当在某一操作步骤中，当前玩家选择传了不同的卡牌。

输入格式

本题单个测试点内有多组测试数据。

第一行输入包含两个整数 $N,T$，其中 $T$ 表示测试数据组数。

接下来描述 $T$ 组数据。每组数据三行：

• 第一行，$2N$ 个正整数，表示玩家 $\text{A}$ 在「发牌」阶段结束后的手牌。
• 第二行，$2N$ 个正整数，表示玩家 $\text{B}$ 在「发牌」阶段结束后的手牌。
• 第三行，$2N$ 个正整数，表示玩家 $\text{C}$ 在「发牌」阶段结束后的手牌。

输出格式

每组数据输出一行一个非负整数，表示答案对 $(10^9+7)$ 取模后的结果。

1 1
1 2
3 3
2 1

2

提示

样例解释

首先，在「弃牌」阶段中，玩家 $\text{B}$ 弃掉了所有卡牌。此时玩家的手牌状态为：

• $\text{A}$：$1$, $2$；
• $\text{B}$：没有牌；
• $\text{C}$：$1$, $2$。

游戏有两种不同的进行方式：

1. $\text{A}$ 将卡牌 $1$ 传给 $\text{B}$，然后 $\text{B}$ 将其传给 $\text{C}$。此时 $\text{C}$ 弃掉数值为 $1$ 的卡牌对。接着 $\text{C}$ 必须将剩余的卡牌传给 $\text{A}$，$\text{A}$ 弃掉该卡牌。
2. $\text{A}$ 将卡牌 $2$ 传给 $\text{B}$，然后 $\text{B}$ 将其传给 $\text{C}$。此时 $\text{C}$ 弃掉数值为 $2$ 的卡牌对。接着 $\text{C}$ 必须将剩余的卡牌传给 $\text{A}$，$\text{A}$ 弃掉该卡牌。

数据范围

对于 $100\%$ 的数据，保证：

• $1\le N\le 99$；
• $1\le T\le 10$。

子任务

注意限制是等于号，不是小于等于号。

编号	$n=$	$T=$	分值
$1$	$2$	$3$	$10$
$2$	$3$	$5$
$3$	$10$
$4$	$20$
$5$	$50$	$10$
$6$	$60$
$7$	$70$
$8$	$80$
$9$	$90$
$10$	$99$