实际上，重（zhòng）庆的正上方就有一个叫轻都的地方。轻都人很轻，而重庆人都很重。在重庆，每个人都有一个飞天梦。

重庆有一个反重力研究中心，那里有正在研发的反重力系统。等研发结束后，准备每年选拔一支队重庆省队，去天上的轻都参加轻都信息学奥林匹克竞赛。

由于重庆省队的名额逐年递减，而反重力系统是 $6$ 年前开始设计的，所以要是今年就结束研发，反重力系统就还能容纳 $6$ 个青鱼有余！

可是，在反重力装置的研发上，许多数学问题还尚未被解决。

例如，反重力装置的核心引擎可以看做是一个由 $n$ 个整数变量 $x_1, \cdots, x_n$ 控制的量子系统，每个变量的值的范围都在 $0$ 到 $T$ 之间（包括 $0$ 和 $T$）。

要想这一系统能够正常运转，需要满足 $m$ 条约束，第 $i$ 条约束形如 $x_{u_i} - x_{v_i} \leq c_i$。

一个物理系统的熵是由其内部所有可能的状态数所决定的。状态数越多，则熵越大。为了估计反重力引擎的熵，反重力研究中心的科学家需要知道有多少种给 $x_1, \cdots, x_n$ 赋值的方案，使得所有约束全部满足。

这可难不倒小青鱼。他一个个地数了起来，但数到 $3$ 的时候就睡着了。没办法，只有让你继续数下去了。

请输出所有可能的给 $x_1, \cdots, x_n$ 赋值的方案数对 $998244353$ 取模的结果。

输入格式

第一行为三个整数 $n, m, T$。

接下来的 $m$ 行，每行三个整数 $u_i, v_i, c_i$。

输出格式

输出一行一个数，表示模 $998244353$ 意义下的答案。

样例一

input

2 5 8
1 2 6
2 1 1
2 1 -1
2 1 0
2 1 0

output

33

样例二

input

3 6 50
1 2 34
1 3 41
2 1 23
2 3 11
3 1 29
3 2 21

output

57217

样例三/四/五

见下发文件。

其中，样例三满足子任务 $7$ 的特殊性质。

数据范围与提示

对于全部数据，$2 \leq n \leq 8, 0 \leq m \leq 200, 0 \leq T \leq 10^{12}, 1 \leq u_i, v_i \leq n, u_i \not= v_i, -T \leq c_i \leq T$。

时间限制：$\texttt{2s}$

空间限制：$\texttt{1GB}$