Sum of GCDs over All Spanning Trees

Given an undirected graph with N vertices and M edges, where the graph may contain multi-edges and self-loops, each edge has an associated weight w. A spanning tree is a collection of N-1 edges that connects all N vertices without forming a cycle. Note that self-loops should not be used in a spanning tree.

Your task is to compute the sum of the greatest common divisors (GCD) of the edge weights for every spanning tree of the graph. In other words, if 𝒯 denotes the set of all spanning trees and for any spanning tree T ∈ 𝒯 with edge weights w_1, w_2, \dots, w_{N-1}, let the value for T be

$$\gcd(w_1,w_2,\dots,w_{N-1}).$$

You are to output the result:

$$\text{Answer} = \left( \sum_{T \in \mathcal{T}} \gcd(w_1,w_2,\dots,w_{N-1}) \right) \bmod 1000000007. $$

See the sample cases for further clarification.

inputFormat

The first line contains two integers N and M — the number of vertices and edges, respectively. Each of the following M lines contains three integers u, v, and w, indicating that there is an edge connecting vertex u and vertex v with weight w. The vertices are 1-indexed. The graph might contain self-loops (i.e. edges where u = v) and multiple edges connecting the same pair of vertices.

outputFormat

Output a single integer — the sum of the GCDs of the edge weights for every spanning tree, taken modulo 1000000007.

sample

3 3
1 2 2
2 3 4
1 3 6

6