题目描述

给定一个由 $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\leq 200$；
• 对于 $50\%$ 的数据，$n\leq 2000$；
• 对于 $70\%$ 的数据，$n\leq 20000$；
• 对于 $100\%$ 的数据，$3\leq n\leq 200000$。