Fishing Game

Fishing is a card game that is played with a deck of cards consisting of $3N$ pairs of cards, numbered from $1$ to $3N$ (the deck contains $6N$ cards overall).

Three friends ($A, B$ and $C$) play Fishing. The rules are as follows:

1. Initially, each player receives $2N$ cards.
2. Then, each player discards all same-value pairs of cards they have.
3. Rounds consisting of three steps are played until all remaining cards get discarded:
   • a) $A$ passes one of his cards to $B$ (unless $A$ doesn't have any). If $B$ now has a pair of same-value cards, it gets discarded.
   • b) $B$ passes one of his cards to $C$ (unless $B$ doesn't have any). If $C$ now has a pair of same-value cards, it gets discarded.
   • c) $C$ passes one of his cards to $A$ (unless $C$ doesn't have any). If $A$ now has a pair of same-value cards, it gets discarded.

Task

You are given the hands of the three players at the end of step (1) . It's known that at least one pair of same-value cards has to be discarded during each round described at point (3).

Compute the number of different ways the game can play out. Since this number can be quite large, output it modulo $1 \ 000 \ 000 \ 007$.

Input data

The first line of input contains two integers $N$ and $T$, where $T$ is the number of game scenarios to analyse.

The description of $T$ game scenarios follows. Each game scenario consists of three lines:

• The first line contains $2N$ card values - player $A$'s hand at the end of step (1).
• The second line contains $2N$ card values - player $B$'s hand at the end of step (1).
• The third line contains $2N$ card values - player $C$'s hand at the end of step (1).

Output data

For each game scenario, print the number of different ways the game can play out modulo $1 \ 000 \ 000 \ 007$ on a separate line.

Constraints and clarifications

• $1 \leq N < 100$
• $1 \leq T \leq 10$
• Two ways the game can play out are considered different if during one step the current player chooses to pass a different card.

Example

stdin

1 1
1 2
3 3
2 1

stdout

2

Explanation

First, during step (2) , player $B$ discards all their cards. At this point, the players' hands are:

• $A: \ 1, 2$
• $B:$ no cards
• $C: \ 1, 2$

There are two ways the game can play out from this point:

1. $A$ passes card $1$ to $B$. Then, $B$ passes it to $C$. This way, $C$ discards the pair of cards with value $1$. Then, $C$ has to pass his remaining card to $A$, who discards it.
2. $A$ passes card $2$ to $B$. Then, $B$ passes it to $C$. This way, $C$ discards the pair of cards with value $2$. Then, $C$ has to pass his remaining card to $A$, who discards it.