一套新桌子刚刚到货,是时候了!办公室里的东西变得相当拥挤。您负责为工程师创建新的座位表。办公桌已编号,您向工程团队发送了一份调查问卷,询问每位工程师他们当前坐在的办公桌编号,以及他们想要坐在的办公桌编号(可能与他们当前的办公桌相同)。每个工程师必须留在原来的位置,或者移动到他们在调查中指定的所需座位。目前,没有两名工程师坐在同一张桌子上,在新的座位安排中,也不可能有两名工程师坐在同一张桌子上。
您可以创建多少个满足指定要求的座位安排?答案可能非常大,因此请以 1000000007 = 109 + 7 为模进行计算。
输入
输入将以包含工程师人数 N (1 ≤ N ≤ 100000) 的行开始。
接下来是 N 行,每行恰好包含两个整数。第i行包含第i个工程师当前的办公桌号和第i个工程师想要移动到的办公桌号。桌子的编号为 1 到 2·N。保证没有两个工程师坐在同一张桌子上。
输出
打印可能的分配数,模 1000000007 = 109 + 7。
示例
输入 #1
4 1 5 5 2 3 7 7 3
输出 #1
6
输入 #2
5 1 10 2 10 3 10 4 10 5 5
输出 #2
5
注意
这些是第一个示例的可能分配:
- 1 5 3 7
- 1 2 3 7
- 5 2 3 7
- 1 5 7 3
- 1 2 7 3
- 5 2 7 3