E - 魔法の道 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 466 点

問題文

高橋君は、N 個の街からなる王国に住んでいます。街には 1 から 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 への一方通行の道は高々 1 本です。なお、街 u から街 v への道と街 v から街 u への道は別々に存在しうることに注意してください。街 u から街 v への道が存在するとき、その魔力値を W(u, v) と書きます。

高橋君は街 1 から出発し、道をちょうど K 回通って街 N にたどり着きたいと考えています。より正確には、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 を経由すること（すなわち v_1, v_2, \ldots, v_{K-1} のいずれかが N であること）も許されます。

経路 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
  • 1 行目には、街の数 N、道の数 M、通る道の本数 K が、スペース区切りで与えられる。
  • 続く M 行で、各道の情報が与えられる（M = 0 の場合、この部分は存在しない）。
  • そのうち i 行目（1 \leq i \leq M）では、i 番目の道の出発地 U_i、到着地 V_i、魔力値 W_i が、スペース区切りで与えられる。

出力

ちょうど K 本の道を通って街 1 から街 N に到着するすべての経路について、総魔力（通った道の魔力値の積）の総和を 998244353 で割った余りを 1 行で出力せよ。条件を満たす経路が 1 つも存在しない場合は 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

Score : 466 pts

Problem Statement

Takahashi lives in a kingdom consisting of N cities. The cities are numbered from 1 to N.

There are several one-way roads between cities, and information about a total of M roads is given. The i-th road (1 \leq i \leq M) is a one-way road from city U_i to city V_i (U_i \neq V_i), and has a non-negative integer W_i called its "magic value". The same ordered pair (U_i, V_i) is never given more than once. That is, for any ordered pair of cities (u, v) (u \neq v), there is at most one one-way road from city u to city v. Note that a road from city u to city v and a road from city v to city u may exist independently. When a road from city u to city v exists, we denote its magic value as W(u, v).

Takahashi wants to start from city 1 and arrive at city N by traversing exactly K roads. More precisely, a sequence of K+1 city numbers v_0, v_1, \ldots, v_K that satisfies all of the following conditions is called a path:

  • v_0 = 1
  • v_K = N
  • For all j = 1, 2, \ldots, K, there exists a road from city v_{j-1} to city v_j

Visiting the same city or traversing the same road multiple times is allowed. Passing through city N along the way (i.e., having N appear among v_1, v_2, \ldots, v_{K-1}) is also allowed.

The total magic of a path v_0, v_1, \ldots, v_K is defined as the product of the magic values of the K roads traversed. That is,

\prod_{j=1}^{K} W(v_{j-1}, v_j)

Takahashi wants to compute the total magic for every possible path and find their sum.

Since this value can be extremely large, find the remainder when divided by 998244353. Here, 998244353 is a prime number. Output the answer as an integer between 0 and 998244352, inclusive.

Constraints

  • 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
  • The same ordered pair (U_i, V_i) is never given more than once
  • All input values are integers

Input

N M K
U_1 V_1 W_1
U_2 V_2 W_2
\vdots
U_M V_M W_M
  • The first line contains the number of cities N, the number of roads M, and the number of roads to traverse K, separated by spaces.
  • The following M lines give the information for each road (if M = 0, this part does not exist).
  • The i-th of these lines (1 \leq i \leq M) contains the starting city U_i, the destination city V_i, and the magic value W_i of the i-th road, separated by spaces.

Output

Output in a single line the remainder when the sum of total magic values (products of the magic values of traversed roads) over all paths that arrive at city N from city 1 by traversing exactly K roads is divided by 998244353. If no path satisfying the conditions exists, output 0.

Sample Input 1

4 4 2
1 2 2
1 3 3
2 4 5
3 4 4

Sample Output 1

22

Sample Input 2

3 1 2
1 2 5

Sample Output 2

0

Sample Input 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

Sample Output 3

63

Sample Input 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

Sample Output 4

0

Sample Input 5

2 0 1

Sample Output 5

0