도미노

은진이는 도미노 게임을 좋아한다. 도미노 조각은 직사각형이며 두 개의 정사각형으로 나뉘어 있다. 각 정사각형에는 0 이상 9 이하의 정수가 하나씩 쓰여 있다. 한 조각에 쓰인 두 숫자는 항상 서로 다르므로 가능한 조각은 모두 45개이다. 조각은 뒤집어서 사용할 수 있으므로, 숫자 1과 2가 들어 있는 조각은 아래 두 모양이 같은 한 조각이다.

+---+---+     +---+---+| 1 | 2 |     | 2 | 1 |+---+---+     +---+---+

안타깝게도 몇몇 조각이 사라졌다. 은진이는 남은 도미노 조각으로 만들 수 있는 사이클 콜렉션이 몇 개인지 알고 싶어 한다.

사이클 콜렉션은 조각을 서로 공유하지 않는 하나 이상의 사이클로 이루어진 집합이다. 하나의 사이클에서는 차례로 놓인 각 조각의 왼쪽 숫자가 바로 앞 조각의 오른쪽 숫자와 같아야 한다. 또한 처음 놓은 조각의 왼쪽 숫자는 마지막 조각의 오른쪽 숫자와도 같아야 한다. 조각은 놓기 전에 뒤집을 수 있다.

+---+---++---+---++---+---++---+---++---+---++---+---+| 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 |+---+---++---+---++---+---+ +---+---++---+---++---+---+

위 그림은 같은 조각의 집합으로 만들 수 있는 세 가지 서로 다른 사이클 콜렉션이다.

어떤 조각은 양옆에 놓인 두 조각과 연결되어 있다고 본다. 사이클에서는 처음 조각과 마지막 조각도 서로 연결되어 있다.

두 사이클은 각 조각이 두 사이클에서 모두 같은 조각들과 연결되어 있을 때 같다. 두 사이클 콜렉션은 포함하는 사이클의 집합이 같을 때 같다.

남은 조각이 주어졌을 때, 모든 조각을 사용해 만들 수 있는 사이클 콜렉션의 개수를 구하는 프로그램을 작성하시오.

첫째 줄에 조각의 개수 N (1 <= N <= 45)이 주어진다. 둘째 줄부터 N개의 줄에는 각 조각이 주어진다. 조각은 두 개의 숫자로 표현되며, 앞의 숫자는 항상 뒤의 숫자보다 작다. 같은 조각은 중복되어 주어지지 않는다.

첫째 줄에 만들 수 있는 사이클 콜렉션의 개수를 출력한다. 이 값은 2^63보다 작다.