分数: 466 分
问题陈述
高桥生活在一个由 N 城市。城市编号从 1 to N.
城市之间有多条单向道路,总共有 给出了 M 道路。的 i第路(1 \leq i \leq M) 是一条从城市出发的单向道路 U_i 前往城市 V_i (U_i \neq V_i),并且有一个非负整数 W_i 称其为“神奇价值”。相同的有序对 (U_i, V_i) 不会出现多次。也就是说,对于任何有序的城市对 (u, v) (u \neq v),距城市最多有一条单向路 u 前往城市 v。请注意,从城市出发的道路 u 前往城市 v 和一条来自城市的道路 v 前往城市 u 可以独立存在。当从城市来的一条路 u 前往城市 v 存在,我们将其魔法值表示为 W(u, v).
高桥想从城市出发 1 并到达城市 N 通过精确遍历 K 道路。更准确地说,是一系列 K+1 城市号码 v_0, v_1, \ldots, v_K 满足以下所有条件的称为 路径:
- v_0 = 1
- v_K = N
- 对于所有人 j = 1, 2, \ldots, K,有一条来自城市的道路 v_{j-1} 前往城市 v_j
允许多次访问同一城市或经过同一条道路。穿过城市 N 一路走来(即,有 N 出现在其中 v_1, v_2, \ldots, v_{K-1})也是允许的。
的 总魔法 路径的 一条路径的 v_0, v_1, \ldots, v_K 被定义为幻值的乘积 K 走过的道路。也就是说,
\prod_{j=1}^{K} W(v_{j-1}, v_j)
高桥想要计算每条可能路径的总魔力并找到它们 总和.
由于该值可能非常大,因此除以求余数 998244353。在这里, 998244353 是质数。将答案输出为介于之间的整数 0 和 998244352,包括在内。
约束
- 2 \leq N \leq 100
- 0 \leq M \leq N(N-1)
- 1 \leq K \leq 10^9
- 1 \leq U_i \leq N
- 1 \leq V_i \leq N
- U_i \neq V_i
- 0 \leq W_i \leq 10^9
- 相同的有序对 (U_i, V_i) 从未给出多次
- 所有输入值均为整数
输入
N M K U_1 V_1 W_1 U_2 V_2 W_2 \vdots U_M V_M W_M
- 第一行包含城市数量 N, 道路数量 M,以及要遍历的道路数量 K,用空格分隔。
- 以下 M 行给出每条道路的信息(如果 M = 0,这部分不存在)。
- 的 i- 这些行(1 \leq i \leq M) 包含起始城市 U_i, 目的地城市 V_i,以及魔法值 W_i 的 i第条路,以空格分隔。
输出
单行输出到达城市的所有路径的总魔法值(走过的道路的魔法值的乘积)总和的余数 N 来自城市 1 通过精确遍历 K 道路除以 998244353。如果不存在满足条件的路径,则输出 0.
示例输入 1
4 4 2 1 2 2 1 3 3 2 4 5 3 4 4
示例输出 1
22
示例输入 2
3 1 2 1 2 5
示例输出 2
0
示例输入 3
5 8 3 1 2 3 1 3 2 2 3 4 2 4 1 3 4 5 3 5 2 4 5 3 4 2 1
示例输出 3
63
示例输入 4
10 15 1000000000 1 2 100 2 3 200 3 4 300 4 5 400 5 6 500 6 7 600 7 8 700 8 9 800 9 10 900 1 5 10 5 10 20 3 7 50 2 10 1000000000 1 10 999999999 7 10 42
示例输出 4
0
示例输入 5
2 0 1
示例输出 5
0