Fishing Game 是一种纸牌游戏，使用一副包含 $3N$ ($1 \le N < 100$) 对牌的牌组进行，牌面数值从 $1$ 到 $3N$（整副牌共有 $6N$ 张）。

三位朋友（A、B 和 C）进行游戏。规则如下：

(1) 初始时，每位玩家获得 $2N$ 张牌。 (2) 然后，每位玩家丢弃手中所有数值相同的对子。 (3) 游戏进行若干轮，每轮包含三个步骤，直到所有剩余的牌都被丢弃： (3a) A 传给 B 一张牌（除非 A 手中没有牌）。如果此时 B 手中有数值相同的对子，则将其丢弃。 (3b) B 传给 C 一张牌（除非 B 手中没有牌）。如果此时 C 手中有数值相同的对子，则将其丢弃。 (3c) C 传给 A 一张牌（除非 C 手中没有牌）。如果此时 A 手中有数值相同的对子，则将其丢弃。

给定步骤 (1) 结束时三位玩家手中的牌。已知在第 (3) 点描述的每一轮中，至少有一对数值相同的牌会被丢弃。

计算游戏进行的不同方式的数量。由于该数字可能非常大，请输出其对 $1\,000\,000\,007$ 取模的结果。

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

输入格式

第一行包含两个整数 $N$ 和 $T$ ($1 \le T \le 10$)，其中 $T$ 是需要分析的游戏场景数量。

接下来是 $T$ 个游戏场景的描述。每个游戏场景包含三行： 第一行包含 $2N$ 个牌面数值，表示步骤 (1) 结束时玩家 A 手中的牌。 第二行包含 $2N$ 个牌面数值，表示步骤 (1) 结束时玩家 B 手中的牌。 第三行包含 $2N$ 个牌面数值，表示步骤 (1) 结束时玩家 C 手中的牌。

输出格式

对于每个游戏场景，在单独的一行中输出游戏进行的不同方式数量，对 $1\,000\,000\,007$ 取模。

子任务

(1) $N = 2, T = 3$ (10 分) (2) $N = 3, T = 5$ (10 分) (3) $N = 10, T = 5$ (10 分) (4) $N = 20, T = 5$ (10 分) (5) $N = 50, T = 10$ (10 分) (6) $N = 60, T = 10$ (10 分) (7) $N = 70, T = 10$ (10 分) (8) $N = 80, T = 10$ (10 分) (9) $N = 90, T = 10$ (10 分) (10) $N = 99, T = 10$ (10 分)

样例

输入 1

1 1
1 2
3 3
2 1

输出 1

2

说明

首先，在步骤 (2) 中，玩家 B 丢弃了他们所有的牌。此时，玩家手中的牌为： A：$1, 2$ B：无牌 C：$1, 2$

从这一点开始，游戏有两种进行方式： (1) A 传给 B 一张牌 $1$。然后，B 将其传给 C。这样，C 丢弃了数值为 $1$ 的对子。然后，C 必须将他剩余的牌传给 A，A 将其丢弃。 (2) A 传给 B 一张牌 $2$。然后，B 将其传给 C。这样，C 丢弃了数值为 $2$ 的对子。然后，C 必须将他剩余的牌传给 A，A 将其丢弃。