题目描述

给定一个无向图，有 $N$ 个顶点和 $M$ 条边。第 $i$ 条边连接了顶点 $A_i$ 和 $B_i$，边的权重为 $C_i$。

初始时，所有的顶点都被涂成黑色。你最多可以进行 $K$ 次以下操作。

• 操作：选择任意一个顶点 $v$ 和任意一个整数 $x$。将通过边的权重最大为 $x$ 的路径从顶点 $v$ 可达的所有顶点都涂成红色，包括 $v$ 自身。

在进行操作后，有多少种顶点集合可以被涂成红色？结果对 $998244353$ 取模。

约束条件

• $2 \leq N \leq 10^5$
• $0 \leq M \leq 10^5$
• $1 \leq K \leq 500$
• $1 \leq A_i,B_i \leq N$
• $1 \leq C_i \leq 10^9$
• 输入中的所有值都是整数。

输入

输入从标准输入给出，格式如下：

$N$ $M$ $K$
$A_1$ $B_1$ $C_1$
$\vdots$
$A_M$ $B_M$ $C_M$

输出

输出答案。

示例输入 1

3 2 1
1 2 1
2 3 2

示例输出 1

6

例如，使用 $(v,x)=(2,1)$ 进行一次操作，将顶点 $1$ 和 $2$ 涂成红色；使用 $(v,x)=(1,0)$ 进行一次操作，将顶点 $1$ 涂成红色。

经过至多一次操作后，可以将顶点涂成红色的集合有以下六种：$\{\},\{1\},\{2\},\{3\},\{1,2\},\{1,2,3\}$。

示例输入 2

5 0 2

示例输出 2

16

给定的图可能不是连通图。

示例输入 3

6 8 2
1 2 1
2 3 2
3 4 3
4 5 1
5 6 2
6 1 3
1 2 10
1 1 100

示例输出 3

40

给定的图可能有重边和自环。