Little W has just learned about spanning trees in his discrete mathematics class: a spanning tree $T$ of an undirected graph $G = (V, E)$ is a subset of the edge set $E$ with size $|V|-1$ such that the subgraph induced by $T$ is connected in $G$.

While doing his homework today, Little W was stumped by the following problem:

Given an undirected graph $G$ with $n$ vertices and $m$ edges (both vertices and edges are numbered starting from $1$), it is guaranteed that the graph contains no multiple edges or self-loops. Each edge has a positive integer weight $w_i$. For a spanning tree $T$ of $G$, the value of $T$ is defined as the greatest common divisor of the weights of the edges in $T$ multiplied by the sum of the weights of the edges in $T$, i.e.:

$$ val(T) = \left(\sum_{i=1}^{n-1} w_{e_i}\right) \times \gcd (w_{e_1}, w_{e_2}, \dots, w_{e_{n-1}}) $$

where $e_1, e_2, \dots, e_{n-1}$ are the indices of the edges contained in $T$.

Little W needs to find the sum of the values of all spanning trees $T$ of $G$. He has been working on it for a long time without success; please help him. Since the answer may be very large, you only need to output the result modulo $998244353$.

Input

The first line contains two positive integers $n$ and $m$, representing the number of vertices and edges in $G$.

The next $m$ lines each contain three positive integers $u_i, v_i, w_i$, where the $i$-th line represents an undirected edge connecting vertex $u_i$ and vertex $v_i$ with weight $w_i$.

Output

Output a single integer representing the result modulo $998244353$.

Examples

Input 1

3 3
1 2 4
2 3 6
1 3 12

Output 1

192

Note 1

$G$ has three spanning trees:

$T_1 = \{(1, 2), (2, 3)\}$, value is $10 \times 2 = 20$.

$T_2 = \{(1, 2), (1, 3)\}$, value is $16 \times 4 = 64$.

$T_3 = \{(1, 3), (2, 3)\}$, value is $18 \times 6 = 108$.

The total sum is $192$.

Input 2

See the provided files.

Subtasks

$10\%$ of the data satisfies: $m \le 15$.

Another $20\%$ of the data satisfies: $m \le n$.

Another $20\%$ of the data satisfies: all $w_i$ are the same.

Another $20\%$ of the data satisfies: all $w_i$ are prime numbers.

$100\%$ of the data satisfies: $2 \le n \le 30, 1 \le m \le \frac {n(n-1)}2, 1 \le w_i \le 152501$.