#P5030. 「长乐集训 2017 Day10」生成树求和
「长乐集训 2017 Day10」生成树求和
Description
给定一张 个点 条边的带权无向图 ,对于 的每一棵生成树,我们定义这棵生成树的权值为:它所包含的所有边的边权按三进制不进位加法相加所得的数。
现在请你求出图 中所有的生成树的权值和(将生成树的权值由三进制转为十进制,做正常的十进制进位加法)。输出答案对 取模后的值即可。
Input Format
第一行两个整数 表示点数与边数。点从 编号。
接下来 行每行三个整数 表示一条连接 的边权为 的无向边。
保证途中不会有重边与自环,边权以十进制形式给出。
Output Format
仅一行一个整数表示答案。
Sample
样例输入
5 7
3 2 7400
4 1 1618
4 2 9110
4 3 4264
5 1 537
5 2 4240
5 3 655
样例输出
262221
Hint
的数据(共六个点),
的数据,