该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定一个由 n 个点、n 条边组成的无向连通图，这张图不存在重边，也不存在自环。请问在这张图上，存在多少条简单路径？

所谓简单，是指路径的起点与终点不相同，且路径上的任何点、任何边都不会在路径上重复出现。所谓重边，是指两条不同的边，连接了同一对点。所谓自环，是指一条边，连接了同一个点。

输入格式

第一行：单个正整数表示 n； 第二行到第 n+1 行：每行两个点 u 和 v，表示一条边连接了编号为 u 与 v 的点。图的结点编号为 1 到 n 之间的整数。

输出格式

单个整数：表示简单路径的条数，由于数字可能很大，输出答案模 10^9 + 7 的余数。

3
1 2
2 3
3 1

12

样例1解释

1->2

2->1

1->3

3->1

2->3

3->2

1->2->3

1->3->2

2->1->3

2->3->1

3->1->2

3->2->1

6
1 2
2 3
3 1
1 4
1 5
2 6

52

数据规模与约定

对于 30% 的数据，n≤200； 对于 50% 的数据，n≤2000； 对于 70% 的数据，n≤20000； 对于 100% 的数据，3≤n≤200000。