题面

juruohjr 所在的城市是可以看成有\(n\)个节点，\(2n\)条有向道路构成的图，每一条边都有编号，而且每一个点恰好有两条入边和两条出边，可能有两条边连接着相同的两个城市并且方向相同，这两条边视为不同的边。
现在闲着没事干的市长 hyf 决定对城市的道路进行精简，他决定删除\(n\)条边，删除之后满足每一个点恰好有一条入边和一条出边，于是他问 juruohjr 有多少种删边方案，但是 juruohjr 实在是太菜了，于是他把问题丢给了大佬您。
我们称两个方案不同，当且仅当存在一条边在一个方案中被选择，而在另一个方案中没有被选择。
答案对\((10^9+7)\)取模。

输入格式

第一行一个数\(n\)，表示城市个数。
第\(2\)行至第\(2n + 1\)行，对于第\(i\)行，两个整数\(u,v\)表示一条从\(u\)到\(v\)的，编号为\(i − 1\)的有向边。

输出格式

一行，一个整数，表示删边的方案数。

样例

Input 1

2
1 2
1 2
2 1
2 1

Output 1

4

解释

删掉\((1,2)\)中删掉一个，\((2,1)\)中删掉一个，那么方案数就是\(4\)。

数据规模

对于20%的数据，满足\(n ≤ 10\);
对于40%的数据，满足\(n ≤ 1 × 10^3\);
对于100%的数据，满足\(1 ≤ n ≤ 1 × 10^5\)。

TIPS

原题提供部分数据答案有误。