Desk Disorder

새 책상들이 마침내 도착했다! 사무실이 상당히 비좁아지고 있던 참이었다. 당신은 엔지니어들의 새로운 좌석 배치표를 만드는 일을 맡았다. 책상에는 번호가 매겨져 있으며, 당신은 엔지니어링 팀을 대상으로 각 엔지니어가 현재 앉아 있는 책상의 번호와 앉고 싶은 책상의 번호를 묻는 설문 조사를 진행했다(두 번호는 같을 수도 있다). 각 엔지니어는 현재 자리에 그대로 남거나 설문 조사에서 지정한 희망 자리로 이동해야 한다. 현재 같은 책상에 앉아 있는 두 엔지니어는 없으며, 새로운 좌석 배치에서도 어떤 두 엔지니어도 같은 책상에 앉을 수 없다.

명시된 조건을 만족하는 좌석 배치를 몇 가지 만들 수 있는가? 답은 매우 클 수 있으므로 1000000007 = 109 + 7로 나눈 나머지를 계산한다.

입력은 엔지니어의 수인 N (1 ≤ N ≤ 100000)이 주어진 한 줄로 시작한다.

이어지는 N개의 줄에는 각각 정확히 두 정수가 주어진다. i-th번째 줄에는 i-th번째 엔지니어가 현재 사용하는 책상의 번호와 i-th번째 엔지니어가 이동하고 싶어 하는 책상의 번호가 주어진다. 책상에는 1부터 2·N까지 번호가 매겨져 있다. 같은 책상에 앉아 있는 두 엔지니어가 없다는 것이 보장된다.

가능한 배정의 수를 1000000007 = 109 + 7로 나눈 나머지를 출력한다.

첫 번째 예제에서 가능한 배정은 다음과 같다.

• 1 5 3 7
• 1 2 3 7
• 5 2 3 7
• 1 5 7 3
• 1 2 7 3
• 5 2 7 3