附加文件请自行下载
小 W 刚刚在离散数学课学习了生成树的知识：一个无向图 的生成树 为边集 的一个大小为 的子集，且保证 的生成子图在 中连通。
小 W 在做今天的作业时被这样一道题目难住了：
给定一个 个顶点 条边（点和边都从 开始编号）的无向图 ，保证图中无重边和无自环。每一条边有一个正整数边权 ，对于一棵 的生成树 ，定义 的价值为： 所包含的边的边权的最大公约数乘以边权之和，即：
其中 为 包含的边的编号。
小 W 需要求出 的所有生成树 的价值之和，他做了很久也没做出来，请你帮帮他。由于答案可能很大，你只需要给出答案对 取模后的结果。