题目描述

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

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

输入格式

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

输出格式

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

数据范围

对于 30% 的数据，n≤200；

对于 50% 的数据，n≤2000；

对于 70% 的数据，n≤20000；

对于 100% 的数据，3≤n≤200000。

样例数据

输入:

3

1 2

2 3

3 1

输出:

12

说明:

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