题目描述

题目译自 Romanian Master of Informatics 2019 Day2 T1 「Fishing Game」

钓鱼是一种纸牌游戏，使用一副包含 $3N$ 对牌的牌组，每张牌的编号从 $1$ 到 $3N$，总共有 $6N$ 张牌。

三个朋友（A，B，C）一起玩钓鱼游戏，规则如下：

1. 游戏开始时，每个人会拿到 $2N$ 张牌。
2. 接着，每个人会丢弃手中所有数值相同的牌对。
3. 然后进入多轮循环，每轮包括三个步骤，直到所有剩余的牌都被丢弃：

• A 将自己的一张牌传给 B（除非 A 手中没牌）。如果 B 因此凑成一对相同数值的牌，这对牌会被丢弃。
• B 将自己的一张牌传给 C（除非 B 手中没牌）。如果 C 因此凑成一对相同数值的牌，这对牌会被丢弃。
• C 将自己的一张牌传给 A（除非 C 手中没牌）。如果 A 因此凑成一对相同数值的牌，这对牌会被丢弃。

你会拿到三个玩家在步骤 1 结束时的手牌。已知在步骤 3 描述的每一轮中，至少有一对相同数值的牌会被丢弃。

你的任务是计算游戏可能进行的不同方式数量。由于这个数字可能很大，结果需要对 $1000000007$ 取模。

如果在某一步中，当前玩家选择了传递不同的牌，则认为这两种游戏方式是不同的。

输入格式

输入的第一行包含两个整数 $N$ 和 $T$ $(1 \leq N < 100, 1 \leq T \leq 10)$，其中 $T$ 表示需要分析的游戏场景数量。

接下来是 $T$ 个游戏场景的描述。每个场景包含三行：

• 第一行包含 $2N$ 个牌的数值，表示玩家 A 在步骤 1 结束时的手牌。
• 第二行包含 $2N$ 个牌的数值，表示玩家 B 在步骤 1 结束时的手牌。
• 第三行包含 $2N$ 个牌的数值，表示玩家 C 在步骤 1 结束时的手牌。

输出格式

对于每个游戏场景，单独一行输出游戏可能进行的不同方式数量，结果对 $1000000007$ 取模。

1 1
1 2
3 3
2 1

2

首先，在步骤 2 中，玩家 B 丢弃了手中所有的牌（3 和 3 是一对）。此时，玩家的手牌情况如下：

• A: $1, 2$
• B: 无牌
• C: $2, 1$

从这一步开始，游戏有两种不同的进行方式：

1. A 将牌 $1$ 传给 B，然后 B 将这张 $1$ 传给 C。这时 C 手中的 $1$ 和 $1$ 凑成一对被丢弃。接着，C 将剩下的牌 $2$ 传给 A，A 手中的 $2$ 和 $2$ 凑成一对被丢弃。
2. A 将牌 $2$ 传给 B，然后 B 将这张 $2$ 传给 C。这时 C 手中的 $2$ 和 $2$ 凑成一对被丢弃。接着，C 将剩下的牌 $1$ 传给 A，A 手中的 $1$ 和 $1$ 凑成一对被丢弃。

因此，游戏有 $2$ 种不同的进行方式。

数据范围与提示

详细子任务附加限制及分值如下表所示。