CF859E.Desk Disorder

A new set of desks just arrived, and it's about time! Things were getting quite cramped in the office. You've been put in charge of creating a new seating chart for the engineers. The desks are numbered, and you sent out a survey to the engineering team asking each engineer the number of the desk they currently sit at, and the number of the desk they would like to sit at (which may be the same as their current desk). Each engineer must either remain where they sit, or move to the desired seat they indicated in the survey. No two engineers currently sit at the same desk, nor may any two engineers sit at the same desk in the new seating arrangement.

How many seating arrangements can you create that meet the specified requirements? The answer may be very large, so compute it modulo 1000000007 = 109 + 7.

一批新办公桌刚刚到货，真是时候！办公室里之前已经相当拥挤了。你被委任负责为工程师们制定一份新的座位安排表。办公桌已编号，你向工程团队发放了一份问卷，询问每位工程师当前所坐的办公桌编号，以及他们希望坐到的办公桌编号（该编号可能与其当前座位编号相同）。每位工程师要么留在原位，要么移动到问卷中指定的目标座位。不允许两位工程师当前坐在同一张办公桌上，也不允许在新的座位安排中出现两位工程师坐在同一张办公桌上的情况。

你能创建多少种满足上述要求的座位安排？答案可能非常大，请对 $1000000007 = 10^9 + 7$ 取模后输出。

Input will begin with a line containing N (1 ≤ N ≤ 100000), the number of engineers.

N lines follow, each containing exactly two integers. The i-th line contains the number of the current desk of the i-th engineer and the number of the desk the i-th engineer wants to move to. Desks are numbered from 1 to 2·N. It is guaranteed that no two engineers sit at the same desk.

输入的第一行包含一个整数 $N$（$1 \leq N \leq 100000$），表示工程师的数量。

接下来有 $N$ 行，每行恰好包含两个整数。第 $i$ 行包含第 $i$ 位工程师当前所在工位的编号以及其希望搬入的工位编号。工位编号范围为 $1$ 到 $2\cdot N$。保证没有两位工程师坐在同一工位上。

Print the number of possible assignments, modulo 1000000007 = 109 + 7.

输出可能的分配方案数，对 $1000000007 = 10^9 + 7$ 取模。

These are the possible assignments for the first example:

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

以下是第一个示例的所有可能分配方案：

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