题目描述

给定一张 $ n $ 个点 $ m $ 条边的带权无向图 $ G $，对于 $ G $ 的每一棵生成树，我们定义这棵生成树的权值为：它所包含的所有边的边权按三进制不进位加法相加所得的数。

现在请你求出图 $ G $ 中所有的生成树的权值和（将生成树的权值由三进制转为十进制，做正常的十进制进位加法）。输出答案对 $ 10 ^ 9 + 7 $ 取模后的值即可。

输入格式

第一行两个整数 $ n, m $ 表示点数与边数。点从 $ 1 \sim n $ 编号。

接下来 $ m $ 行每行三个整数 $ a, b, c $ 表示一条连接 $ (a, b) $ 的边权为 $ c $ 的无向边。

边权以十进制形式给出。

输出格式

仅一行一个整数表示答案。

样例

input

5 7
3 2 7400
4 1 1618
4 2 9110
4 3 4264
5 1 537
5 2 4240
5 3 655

output

262221

数据范围与提示

$ 30 \% $ 的数据（共六个点）：$ n = 5, 6, 7, 8, 9, 10 $
$ 50 \% $ 的数据：$ n \le 30 $
$ 70 \% $ 的数据：$ n \le 40 $
$ 100 \% $ 的数据：$ n \le 100, m \le \frac{n(n-1)}{2}, 0 \leq c \leq 10 ^ 4 $，保证无重边无自环。