Description

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

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

Input Format

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

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

保证途中不会有重边与自环，边权以十进制形式给出。

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

$30 \%$ 的数据(共六个点)，$n = 5, 6, 7, 8, 9, 10$

$100 \%$ 的数据，$n \leq 40, 0 \leq c \leq 10 ^ 4$