UOJ Logo Universal Online Judge

UOJ

附件下载 统计

实际上,重(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$。

子任务编号 $n \leq$ 特殊性质 分值
$1$ $3$ $T\leq 200$ $5$
$2$ $2$ $5$
$3$ $3$ $15$
$4$ $4$ $15$
$5$ $5$ $10$
$6$ $6$ $20$
$7$ $7$ $u_i - v_i \in \{-1, 1\}$ $10$
$8$ $10$
$9$ $8$ $10$

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

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