An undirected graph with no multiple edges and no self-loops is called a simple undirected graph.

Given a simple undirected graph $G$ with $n$ vertices and $m$ edges. If we assign an integer value to each edge of $G$ as its weight, such that each edge weight is between $1$ and $m$, and all edge weights are distinct, such an assignment is called a labeling of $G$.

Two labelings $G_0$ and $G_1$ are called equivalent if and only if for every subgraph $G'$ of $G$, the minimum spanning forest under both labelings has the same shape (i.e., they are the same subgraph when ignoring edge weights).

Given a labeling $G_0$ of $G$, find the number of labelings equivalent to it, modulo $998244353$.

The minimum spanning forest of a positively weighted undirected graph is the subgraph with the same number of connected components as the original graph and the minimum possible sum of edge weights. It can be proven that if all edge weights are distinct, such a subgraph is unique.

Input

Read data from standard input.

The first line contains two integers $n, m$.

The next $m$ lines each contain three integers $x, y, z$, representing an edge between $x$ and $y$ in $G_0$ with weight $z$.

It is guaranteed that each edge weight is between $1$ and $m$, and all edge weights are distinct.

Output

Output to standard output.

The first line contains an integer $ans$, representing the answer modulo $998244353$.

Examples

Input

4 6
1 2 1
1 3 2
1 4 4
2 3 3
2 4 6
3 4 5

Output

8

Note

There are the following eight labeling methods (the order of edges is consistent with the input):

• $[1,2,3,4,6,5]$
• $[1,2,4,3,6,5]$
• $[1,3,2,4,6,5]$
• $[2,1,3,4,6,5]$
• $[2,1,4,3,6,5]$
• $[2,3,1,4,6,5]$
• $[3,1,2,4,6,5]$
• $[3,2,1,4,6,5]$

Subtasks

For all data: $1\leq n, m\leq 2\times 10^5$.

$\text{Subtask 1}\ (10\%)$: $n\leq 12,\ m\leq 6$.

$\text{Subtask 2}\ (15\%)$: $n, m\leq 200$.

$\text{Subtask 3}\ (20\%)$: $n\leq 2000$.

$\text{Subtask 4}\ (2\%)$: $G$ is a tree.

$\text{Subtask 5}\ (13\%)$: $G$ is a cactus graph.

$\text{Subtask 6}\ (15\%)$: $G$ is a diamond graph.

$\text{Subtask 7}\ (25\%)$: No special restrictions.

Below are explanations for some of the graph theory terms used above.

Tree: A simple undirected connected graph with no simple cycles.

Cactus graph: A simple undirected connected graph where any edge belongs to at most one simple cycle.

Diamond graph: A simple undirected connected graph with exactly $n-2$ vertices of degree $2$.