Description

Xiao Y has an undirected graph with $N$ vertices and $M$ edges (possibly with multiple edges and self-loops), and each edge has a weight $w$.

You need to compute the sum of the greatest common divisors of the edge weights over all spanning trees; see the sample for details.

Since the answer may be large, take it modulo $1000000007$.

Input Format

The first line contains two positive integers $N, M$, denoting the number of vertices and the number of edges.

The next $M$ lines each contain three positive integers $u, v, w$, denoting an edge connecting $u$ and $v$ with weight $w$.

Output Format

Output a single integer: the answer modulo $1000000007$.

4 5  
1 2 12  
1 3 9  
2 4 6  
3 4 8  
1 4 4  

15

Hint

Explanation of Sample $1$

Obviously, this graph has $8$ different spanning trees.

Let $\gcd(x,y,z)$ denote the greatest common divisor of $x, y, z$. Then the answer is

$\gcd(12,6,8)+\gcd(6,8,9)+\gcd(8,9,12)+\gcd(9,12,6)+\gcd(9,4,6)+\gcd(12,4,8)+\gcd(12,4,9)+\gcd(6,4,8)$

$=2+1+1+3+1+4+1+2$

$=15$.

Constraints

For $20\%$ of the testdata, $N\le 10, M\le 20$;

For another $10\%$ of the testdata, $N\le 12, M\le 24$;

For another $20\%$ of the testdata, $N\le 60, M\le 3000$, and it satisfies $u_i+1=v_i$;

For another $20\%$ of the testdata, $N\le 40, M\le 1000, W\le 1000$;

For another $15\%$ of the testdata, $N\le 50, M\le 2000$;

For $100\%$ of the testdata, $N\le 60, M\le 3000, W\le 1000000$.

Translated by ChatGPT 5