[Hidden ☆ before use]
#### 1293. I. Lineup the Dominoes

#### Description

Consider a game of solitary dominoes, where you are given several dominoes with a number of dots on both sides, with the number of dots ranging from 1 to 6, inclusive, and the goal is to line up the dominoes from left to right such that all touching sides between dominoes share the same number of dots. Here is a valid solution with a set of three dominoes:

Given dominoes D_{1} through D_{n}, we consider a solution to be different than another solution if at least one domino is in a different location in the two solutions. Also, we allow dominoes to be flipped so, for example, a domino that reads 5, 2 from left to right can also be placed to read 2, 5 from left to right by flipping it. Note that for two solutions to be different, only the positions of dominoes matter, i.e., the values on the dominoes and the orientation of each domino does not matter. For example, let’s assume D_{1}=[4,4] and D_{2}=[4,4]; the solution {D_{1}, D_{2}} is different from the solution {D_{2}, D_{1}} even though both solutions represent the same pattern: {D_{1}, D_{2}}=[4,4][4,4] and {D_{2}, D_{1}}=[4,4][4,4]. But the solution {D_{1}, D_{2}} is not different from any other {D_{1}, D_{2}} even if we flip one or both dominoes.

Using the three dominoes above, multiple solutions exist. One solution is shown above; another solution is D_{1}, D_{3} and D_{2}, in sequence. We can get the latter to work by flipping both D_{2} and D_{3} compared to how they are shown above. Note again that these two solutions are different since one solution is {D_{1}, D_{2}, D_{3}} and one is {D_{1}, D_{3}, D_{2}}, i.e., the position of D_{2} has changed (and position of D_{3} as well).

The Problem:

Given a set of dominoes, count the number of different solutions to the domino puzzle. As previously described, a correct solution will arrange all the dominoes in a line such that all touching sides between dominoes share the same number of dots. Since the number of solutions may be very large, calculate it mod 10^{9} + 7.

#### Input

The first input line contains a single positive integer, m (1 ≤ m ≤ 100), indicating the number of sets of dominoes to evaluate. This is followed by the data for these sets of dominoes.

The first line of input for each set of dominoes will contain an integer, n (1 ≤ n ≤ 16), the number of dominoes for that set. Each of the following n lines will contain two space separated integers, s_{i} (1 ≤ s_{i }≤ 6) and t_{i} (1 ≤ t_{i }≤ 6), representing the number of dots on each side of the i^{th} domino.

#### Output

For each set of dominoes, on a line by itself, output the number of different solutions to the domino puzzle mod 10^{9 }+ 7.

#### Samples

#### Source

UCF2016

Given dominoes D

Using the three dominoes above, multiple solutions exist. One solution is shown above; another solution is D

The Problem:

Given a set of dominoes, count the number of different solutions to the domino puzzle. As previously described, a correct solution will arrange all the dominoes in a line such that all touching sides between dominoes share the same number of dots. Since the number of solutions may be very large, calculate it mod 10

The first line of input for each set of dominoes will contain an integer, n (1 ≤ n ≤ 16), the number of dominoes for that set. Each of the following n lines will contain two space separated integers, s

Input
Copy

5 3 1 5 5 2 2 5 2 1 3 4 5 3 1 2 3 4 1 4 4 1 1 1 1 1 1 1 1 4 3 5 3 5 3 5 3 5

Output

4 0 2 24 24

Time Limit: | 10000MS (C/C++,Others×2) |

Memory Limit: | 1024MB (C/C++,Others×2) |

Special Judge: | No |

AC/Submit: | 1 / 1 |

Tags: |