称无重边，无自环的无向图为简单无向图。

给定一个 $n$ 个点 $m$ 条边的简单无向图 $G$。若我们给 $G$ 的每条边指定一个整数值作为边权。满足每条边的边权都在 $1$ 到 $m$ 之间，且每条边的边权两两不同，则称这样的指定方法为 $G$ 的一个赋值。

两个赋值 $G_0,G_1$ 称为等价的，当且仅当对于 $G$ 的每个子图 $G'$，其在两种赋值下的最小生成森林形状相同（即在忽略边权的情况下是同一个子图）。

给定一个 $G$ 的赋值 $G_0$，求与它等价的赋值的数量，答案对 $998244353$ 取模。

一个带正权的无向图的最小生成森林，是指连通块数与原图相同的边权和最小的子图，可以证明，如果每条边的边权两两不同，那么这样的子图是唯一的。

输入格式

从标准输入读入数据。

第一行：两个整数 $n,m$。

接下来 $m$ 行：每行三个整数 $x,y,z$，表示 $G_0$ 中 $x,y$ 之间有一条边权为 $z$ 的边。

保证每条边的边权都在 $1$ 到 $m$ 之间，且所有边权两两不同。

输出格式

输出到标准输出。

第一行：一个整数 $ans$，表示答案对 $998244353$ 取模。

样例

输入

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

输出

8

解释

有如下八种赋值方式（边的顺序与输入一致）：

• $[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]$

子任务

对于全部数据：$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$ 是树。

$\text{Subtask 5}\ (13\%)$：$G$ 是仙人掌。

$\text{Subtask 6}\ (15\%)$：$G$ 是杏仁。

$\text{Subtask 7}\ (25\%)$：无特殊限制。

下面是对上面一些图论术语的解释。

树：没有简单环的简单无向连通图。

仙人掌：任何一条边在至多一个简单环上的简单无向连通图。

杏仁：恰好有 $n-2$ 个点的度数为 $2$ 的简单无向连通图。