小 W 刚刚在离散数学课学习了生成树的知识:一个无向图 的生成树 为边集 的一个大小为 的子集,且保证 的生成子图在 中连通。
小 W 在做今天的作业时被这样一道题目难住了:
给定一个 个顶点 条边(点和边都从 开始编号)的无向图 ,保证图中无重边和无自环。每一条边有一个正整数边权 ,对于一棵 的生成树 ,定义 的价值为: 所包含的边的边权的最大公约数乘以边权之和,即:
其中 为 包含的边的编号。
小 W 需要求出 的所有生成树 的价值之和,他做了很久也没做出来,请你帮帮他。由于答案可能很大,你只需要给出答案对 取模后的结果。
输入格式
第一行两个正整数 ,表示 的点数和边数。
接下来 行,每行三个正整数 ,第 行表示一条无向边连接 号点和 号点,权值为 。
输出格式
一行一个整数,表示答案对 取模后的结果。
样例1
input
3 3
1 2 4
2 3 6
1 3 12
output
192
explanation
共有三棵生成树:
,价值为 。
,价值为 。
,价值为 。
总和为 。
样例2
见附加文件中 ex_count2.in
与 ex_count2.ans
。
数据范围
对于前 的数据满足:。
另有 的数据满足:。
另有 的数据满足: 均相同。
另有 的数据满足: 均为质数。
对于 的数据满足:。
时间限制:
空间限制: