CF859E Desk Disorder

一批新办公桌刚刚送到，正好适合现在的需求！办公室里的工位已经变得非常拥挤了。你被任命为为工程师们分配新的座位表。办公桌都按编号排列，你向工程师团队发放了一份调查问卷，询问每位工程师当前所在的桌号，以及他们希望坐的桌号（可能和当前相同）。每位工程师必须要么留在原座位，要么搬到调查中提出的目标座位。当前没有两位工程师坐在同一张桌子上，新的座位安排中也不允许两位工程师坐在同一张桌子上。 你能满足要求的分配方案有多少种？由于答案可能非常大，请输出答案对 $1000000007=10^{9}+7$ 取模后的结果。

输入的第一行为一个整数 $N$，表示工程师的人数，$1 \leq N \leq 100000$。 接下来有 $N$ 行，每行两个整数，第 $i$ 行表示第 $i$ 位工程师当前坐的桌子编号以及他们希望去的桌子编号。桌子编号从 $1$ 到 $2N$。保证当前没有两位工程师坐在同一张桌子上。

输出满足条件的分配方案数，对 $1000000007=10^{9}+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 由 ChatGPT 5 翻译