给定一个有 $N$ 个顶点、$M$ 条边的有向图 $G$ 以及一个正整数 $K$。

在 $G$ 中，顶点和边分别编号为顶点 $1$、顶点 $2$、...、顶点 $N$ 以及边 $1$、边 $2$、...、边 $M$。第 $i$ 条边（$1 \leq i \leq M$）是从顶点 $u_i$ 指向顶点 $v_i$ 的边，附加有参数 $b_i$，其中 $b_i$ 为 $0$ 或 $1$。

有向图 $G$ 满足以下三个条件：

• $G$ 不包含重边。
• $G$ 不包含环。
• 每个顶点都能通过若干条边从顶点 $1$ 出发到达，且顶点 $1$ 到每个顶点的最短路径长度与最长路径长度相等，且均不超过 $K$。

两名玩家使用各自的一枚棋子进行如下博弈：

• 一开始，每位玩家都将自己的棋子放置在顶点 $1$ 上。
• 在自己的回合，玩家可以进行以下两种操作之一：
  • 移动：将自己的棋子恰好移动一次。若己方棋子处于顶点 $i$，则只能将其移动到有边指向的顶点 $j$ 上。当己方棋子在顶点 $1$ 时，必须等概率且随机地选择一条可以到达的边移动。注意，先手玩家可以使用所有边，后手玩家只能使用 $b_i=0$ 的边。
  • 宣布失败：主动认输，结束游戏，本方负，对方胜。
• 由先手玩家开始，双方轮流操作。如果无人宣布失败，在后手玩家完成第 $K$ 次移动操作后，游戏结束。此时，如果两枚棋子位于同一顶点，则后手获胜，否则先手获胜。

每位玩家都以胜利为目标采取最优策略。
请计算先手玩家获胜的概率 $\bmod\ 998244353$。

概率 $\bmod\ 998244353$ 的定义如下：可以证明本题要求的概率一定是有理数，并且在本题的限制下，若该概率为既约分数 $\frac{y}{x}$，则 $x$ 一定与 $998244353$ 互质。此时，存在唯一的 $0 \leq z < 998244353$ 满足 $y \equiv xz \pmod{998244353}$，请输出 $z$。

输入从标准输入读入，格式如下：

$N$ $M$ $K$ $u_1$ $v_1$ $b_1$ $u_2$ $v_2$ $b_2$ $\vdots$ $u_M$ $v_M$ $b_M$

输出先手玩家获胜的概率 $\bmod\ 998244353$。

小题点

1.（$1$ 分）$N\leq 100$，$M\leq 1000$
2.（$99$ 分）无附加限制

样例解释 1

每位玩家各自移动棋子一次后，记先手所在顶点为 $i$，后手所在顶点为 $j$，所有可能的 $(i,j)$ 组合中，先手胜利与后手胜利的组合分别如下：

• 先手胜利：$(2,3)$、$(3,3)$
• 后手胜利：$(2,2)$、$(3,2)$

如当选择到 $(3,2)$ 时，游戏进程可能如下：

• 首先将棋子放在顶点 $1$。
• 先手使用边 $2$ 将棋子移到顶点 $3$。
• 后手使用边 $1$ 将棋子移到顶点 $2$。
• 先手使用边 $6$ 将棋子移到顶点 $5$。
• 后手使用边 $4$ 将棋子移到顶点 $5$。
• 后手完成第 $2$ 次移动，游戏结束。两枚棋子都在顶点 $5$，后手胜利。

此外，在 $ (3,2)$ 情况下，无论先手采取何种策略，后手都能获胜。

故先手胜率为 $\frac{1}{2}$，模 $998244353$ 取值为 $499122177$。

此样例满足小题 $1$ 的限制。

样例解释 2

每位玩家各自移动棋子一次后，记先手所在顶点为 $i$，后手所在顶点为 $j$，所有可能的 $(i,j)$ 组合中，先手胜利与后手胜利的组合分别如下：

• 先手胜利：$(2,3)$、$(3,2)$、$(3,3)$
• 后手胜利：$(2,2)$

如当选择到 $(3,2)$ 时，游戏进程可能如下：

• 首先将棋子放在顶点 $1$。
• 先手使用边 $2$ 将棋子移到顶点 $3$。
• 后手使用边 $1$ 将棋子移到顶点 $2$。
• 先手使用边 $5$ 将棋子移到顶点 $5$。
• 后手使用边 $3$ 将棋子移到顶点 $4$。
• 后手完成第 $2$ 次移动，游戏结束。此时两枚棋子位于不同顶点，先手胜利。

此外，在 $ (3,2)$ 情况下，无论后手采取何种策略，先手都能获胜。

先手胜率为 $\frac{3}{4}$，模 $998244353$ 取值为 $249561089$。

此样例满足小题 $1$ 的限制。

样例解释 3

后手必须在未进行任何移动时宣布失败。

此样例满足小题 $1$ 的限制。

样例解释 4

此样例满足小题 $1$ 的限制。

数据范围

• $2 \leq N \leq 4000$
• $1 \leq M \leq 2 \times 10^{6}$
• $1 \leq K \leq 4000$
• $1 \leq u_i, v_i \leq N$
• $b_i \in \{0, 1\}$
• $G$ 不含重边。
• $G$ 不含环。
• 每个顶点都能通过若干条边从顶点 $1$ 出发到达，且顶点 $1$ 到每个顶点的最短路径长度与最长路径长度相等，且均不超过 $K$。
• 所有输入均为整数。

由 ChatGPT 5 翻译