AT_abc213_h [ABC213H] Stroll

[problemUrl]: https://atcoder.jp/contests/abc213/tasks/abc213_h 高橋君は家の周りをあてもなく歩き回ることにしました。 散歩の間、高橋君は地点 $ 1 $, 地点 $ 2 $, $ \dots $, 地点 $ N $ の $ 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 $ で割ったあまりを求めてください。ただし、$ 2 $ つの散歩コースは列として異なるときに異なるとみなされます。

入力は以下の形式で標準入力から与えられる。 > $ 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\ \lt\ b_i\ \leq\ N $ - $ i\ \neq\ j $ ならば $ (a_i,\ b_i)\ \neq\ (a_j,\ b_j) $ - $ 0\ \leq\ p_{i,j}\ \lt\ 998244353 $ ### Sample Explanation 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 $ 通りです。 ### Sample Explanation 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 $ の $ 5 $ パターンがあり、本数は上から順に $ 81 $ 通り、 $ 6 $ 通り、 $ 36 $ 通り、 $ 1 $ 通り、 $ 6 $ 通りとなります。