D. Graph of Maximum Degree 3
time limit per test
1.5 s
memory limit per test
1024 megabytes
input
standard input
output
standard output

Bobo recently obtained a (undirected) graph $$$G=(V, E)$$$. He noticed that each edge of this graph is colored either red or blue, and the maximum degree of this graph is not greater than $$$3$$$.

Now, Bobo wonders how many nonempty induced subgraphs $$$G[S]=(S, E')$$$ of $$$G$$$ are there, such that the two following conditions are satisfied:

  • The graph formed by keeping only the red edges of $$$G[S]$$$ is connected.
  • The graph formed by keeping only the blue edges of $$$G[S]$$$ is also connected.

As the answer might be too large, you need to output the result modulo $$$998\,244\,353$$$ (a prime number).

Refer to the note section for formal definitions of the underlined items and more illustrations.

Input

The first line contains two integers $$$n$$$ $$$(1\leq n\leq 10^5)$$$ and $$$m$$$ $$$(0\leq m\leq 1.5\times 10^5)$$$, denoting the number of vertices and edges in the graph $$$G$$$, respectively.

Then $$$m$$$ lines follows, each line containing three integers $$$u,v,c$$$ $$$(1\leq u,v\leq n,u\neq v,c\in \{0,1\})$$$, denoting there is an edge $$$(u,v)$$$, with color red if $$$c=0$$$ and color blue otherwise.

It is guaranteed that the maximum degree of $$$G$$$ is at most $$$3$$$, and no two edges with the same color connect the same pair of vertices. Please be aware that multiple edges in $$$G$$$ with different colors may still exist.

Output

Output an integer in a line, denoting the number of induced subgraphs satisfying the required conditions, taken modulo $$$998\,244\,353$$$.

Examples
Input
3 4
1 2 0
1 3 1
2 3 0
2 3 1
Output
5
Input
4 6
1 2 0
2 3 0
3 4 0
1 4 1
2 4 1
1 3 1
Output
5
Note

Here, we provide formal definitions of some underlined items in the statement.

  • The degree of a vertex of a graph is the number of edges that are incident to the vertex.
  • The maximum degree of a graph $$$G$$$ is the maximum of its vertices' degrees;
  • An induced subgraph of a graph $$$G=(V, E)$$$ is another graph $$$G[S]=(S, E')$$$, formed from a subset $$$S$$$ of the vertices of the graph and all of the edges $$$E'$$$ (from the original graph $$$G$$$) connecting pairs of vertices in that subset $$$S$$$. An induced graph $$$G[S]$$$ is nonnempty if and only if $$$S\neq \varnothing$$$.
  • A graph is said to be connected if every pair of vertices in the graph is connected, i.e., there is a path between every pair of vertices.

The following picture lists the graph $$$G=(V, E)$$$ and all its seven nonempty induced subgraphs for the first sample test. Here, solid lines represent the red edge, while the dashed lines represent the blue ones. Five nonempty induced subgraphs satisfy the required condition, which are $$$G[\{1\}], G[\{2\}], G[\{3\}], G[\{2,3\}]$$$ and $$$G[\{1,2,3\}]$$$, respectively.