AT_abc213_h [ABC213H] Stroll

高桥君决定在家附近随意散步。 在散步过程中，高桥君会在 $N$ 个地点（地点 $1$、地点 $2$、$\dots$、地点 $N$）之间来回走动。其中，地点 $1$ 是他的家。 有 $M$ 对地点之间存在道路。对于第 $i$ 对地点 $(a_i, b_i)$，地点 $a_i$ 和地点 $b_i$ 之间有长度为 $d$（$1 \leq d \leq T$）公里的道路各 $p_{i,d}$ 条，这些道路是双向的。 高桥君想知道，从家出发，走 $T$ 公里后回到家的散步路线有多少种。这里，长度为 $T$ 公里的散步路线定义如下： - 存在一个交替排列地点和道路的序列 $v_0 = 1, e_0, v_1, \dots, e_{k-1}, v_k = 1$，其中 $e_i$（$0 \leq i \leq k-1$）连接 $v_i$ 和 $v_{i+1}$，且所有 $e_i$ 的长度之和为 $T$ 公里。 请你帮高桥君计算满足条件的散步路线数量，并对 $998244353$ 取模输出。注意，当两个路线的序列不同，则认为是不同的路线。

输入通过标准输入给出，格式如下： > $N$ $M$ $T$ > $a_1$ $b_1$ $p_{1,1}$ $p_{1,2}$ $\ldots$ $p_{1,T}$ > $\vdots$ > $a_M$ $b_M$ $p_{M,1}$ $p_{M,2}$ $\ldots$ $p_{M,T}$

输出满足条件的散步路线数量，对 $998244353$ 取模。

## 限制条件 - $2 \leq N \leq 10$ - $1 \leq M \leq \min\left(10, \frac{N(N-1)}{2}\right)$ - $1 \leq T \leq 4 \times 10^4$ - $1 \leq a_i < b_i \leq N$ - 若 $i \neq j$，则 $(a_i, b_i) \neq (a_j, b_j)$ - $0 \leq p_{i,j} < 998244353$ ## 样例解释 1 高桥君家附近有： - 连接地点 $1$ 和地点 $2$ 的长度为 $1$ 公里的道路 $1$ 条 - 连接地点 $1$ 和地点 $3$ 的长度为 $1$ 公里的道路 $2$ 条 满足条件的路线有： - 按 $1 \to 2 \to 1$ 顺序的路线有 $1 \times 1 = 1$ 种 - 按 $1 \to 3 \to 1$ 顺序的路线有 $2 \times 2 = 4$ 种 共计 $5$ 种。 ## 样例解释 2 高桥君家附近有： - 连接地点 $1$ 和地点 $2$ 的长度为 $1$ 公里的道路 $3$ 条 - 连接地点 $1$ 和地点 $3$ 的长度为 $2$ 公里的道路 $1$ 条 - 连接地点 $2$ 和地点 $3$ 的长度为 $1$ 公里的道路 $2$ 条 满足条件的路线，按经过的地点列举如下： - $1 \to 2 \to 1 \to 2 \to 1$ - $1 \to 2 \to 3 \to 1$ - $1 \to 2 \to 3 \to 2 \to 1$ - $1 \to 3 \to 1$ - $1 \to 3 \to 2 \to 1$ 对应的路线数分别为 $81$、$6$、$36$、$1$、$6$ 种。 由 ChatGPT 4.1 翻译