Dominoes

Time limit

Memory limit

128 MB

Problem

Eunjin likes playing dominoes. A domino is a rectangle divided into two squares, and each square contains one integer from 0 through 9. The two numbers on a piece are always different, so there are 45 possible pieces. A piece may be flipped; for example, the piece containing 1 and 2 is the same piece in both orientations below.

Some of the pieces have been taken away. With the remaining pieces, Eunjin wants to know how many cycle collections can be made.

A cycle collection is a set of one or more cycles that do not share pieces. In a cycle, the left number of each placed piece is equal to the right number of the previous placed piece. The left number of the first piece must also be equal to the right number of the last piece. Pieces may be flipped before being placed.

+---+---++---+---++---+---++---+---++---+---++---+---+| 1 | 2 || 2 | 5 || 5 | 4 || 4 | 2 || 2 | 8 || 8 | 1 |+---+---++---+---++---+---++---+---++---+---++---+---++---+---++---+---++---+---++---+---++---+---++---+---+| 1 | 2 || 2 | 4 || 4 | 5 || 5 | 2 || 2 | 8 || 8 | 1 |+---+---++---+---++---+---++---+---++---+---++---+---++---+---++---+---++---+---+ +---+---++---+---++---+---+| 1 | 2 || 2 | 8 || 8 | 1 | | 4 | 5 || 5 | 2 || 2 | 4 |+---+---++---+---++---+---+ +---+---++---+---++---+---+

+---+---++---+---++---+---++---+---++---+---++---+---+| 1 | 2 || 2 | 5 || 5 | 4 || 4 | 2 || 2 | 8 || 8 | 1 |+---+---++---+---++---+---++---+---++---+---++---+---++---+---++---+---++---+---++---+---++---+---++---+---+| 1 | 2 || 2 | 4 || 4 | 5 || 5 | 2 || 2 | 8 || 8 | 1 |+---+---++---+---++---+---++---+---++---+---++---+---++---+---++---+---++---+---+ +---+---++---+---++---+---+| 1 | 2 || 2 | 8 || 8 | 1 | | 4 | 5 || 5 | 2 || 2 | 4 |+---+---++---+---++---+---+ +---+---++---+---++---+---+

The diagram above shows three different cycle collections that can be made from the same set of pieces.

A piece is connected to the two pieces surrounding it. The first and last pieces of a cycle are also connected.

Two cycles are the same if every piece is connected to the same pieces in both cycles. Two cycle collections are the same if they contain the same set of cycles.

Given the remaining pieces, write a program that counts how many cycle collections can be made. Every given piece must be used.

Input

The first line contains the number of pieces, N (1 <= N <= 45). Each of the next N lines contains one piece. A piece is written as two digits, and the first digit is always smaller than the second digit. No piece appears more than once.

Output

Print the number of cycle collections that can be made. This value is less than 2^63.