白夜
题号：NC211999
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述


给定一张  个点  条边的简单无向图，其中每条边的边权均为在  中独立随机的一个实数，你需要计算这张图的最小生成树的边权和的平方的期望值。

可以证明，答案一定是一个有理数。所以你只需要输出答案对  取模的结果。

输入描述:

第一行两个正整数依次表示 

接下来  行，每行两个正整数   表示一条连接  号点和  号点的无向边。

输出描述:

共一行一个正整数，表示期望的权值和对  取模的结果。
示例1

输入

复制 
3 2
1 2
2 3

输出

复制 
166374060

说明

答案为 7/6
示例2

输入

复制 
4 3
1 2
2 3
3 4

输出

复制 
499122179

说明

答案为 5/2
示例3

输入

复制 
5 6
1 2
2 3
3 4
4 5
1 5
2 5

输出

复制 
216880472

说明

相信聪明的你一定可以徒手算出这个样例的真实答案。
示例4

输入

复制 
4 4
1 2
2 3
3 4
1 4

输出

复制 
665496237

说明

相信聪明的你一定可以徒手算出这个样例的真实答案。

备注:

，且