交通

题面

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

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

信息

ID
1079
难度
10
分类
(无)
标签
(无)
递交数
1
已通过
0
通过率
0%
上传者