Fishing Game

The game "Fishing Game" is played with a deck consisting of \(3N\) pairs of cards (i.e. \(6N\) cards in total) numbered from \(1\) to \(3N\). Three friends, A, B and C, participate in the game. After the Dealing phase each player gets \(2N\) cards and then discards any pair of cards with the same number in his own hand. Hence, after discarding, every remaining card in a player’s hand is unique, and for every remaining card number, its matching card is held by a different player. It turns out that the only possible remaining pairs are those that are split between players A and B, B and C, or C and A. In particular, if we denote the pair that will eventually be discarded on the move from A \(\to\) B by type AB, from B \(\to\) C by type BC, and from C \(\to\) A by type CA, it can be proved that each player ends up with exactly \(N\) cards from one type and \(N\) cards from another, so that each player’s hand has \(2N\) cards.

In the subsequent Playing phase the following cyclic moves occur repeatedly until all cards are discarded:

1. A passes one card to B (unless A has no card). If at that moment B already holds a card with the same number, then the two matching cards are immediately discarded.
2. B passes one card to C (unless B has no card). If C already holds a matching card, they are immediately discarded.
3. C passes one card to A (unless C has no card). If A already holds a matching card, then the two matching cards are immediately discarded.

Moreover, it is guaranteed that in every complete cycle of three moves at least one pair is discarded. Two game processes are considered different if, at some move, the player whose turn it is passes a different card. Given the state of the players’ hands after the dealing phase (i.e. after the initial discarding), compute the number of different complete game processes modulo \(10^9+7\).

Note: In the input the hands are given for players A, B and C in that order. Each hand has exactly \(2N\) numbers. It is guaranteed that within each hand no number appears twice (since any pair in one hand would have been discarded during the dealing phase), and for each number present in the hands its duplicate appears in a different player’s hand.

inputFormat

The first line contains a single integer \(N\) (\(1 \le N \le 5\), note that given the simulation nature, the input size is small).

The next three lines describe the hands of players A, B, and C respectively. Each of these lines contains \(2N\) space‐separated positive integers. For every number appearing in one hand, its matching number appears in one of the other two hands.

outputFormat

Output a single integer, the number of different complete game processes modulo \(10^9+7\).

sample

1
1 3
1 2
2 3

1