Expected Minimum Arborescence Cost

We are given (n) cities and (m) directed roads. The (i)th road goes from (u_i) to (v_i) with a positive integer cost (w_i). Due to an emergency, before any road is built, we must immediately choose a subset of these roads to construct so that people from every city can travel (using the constructed roads) to at least one of a set of (k) destination cities. However, the (k) destination cities are chosen uniformly at random among the (n) cities. For each possible set (S) of (k) cities, let (f(S)) be the minimum total cost of the roads we have to build such that, for every city (v), there exists a (possibly empty) path from (v) to some city (u \in S). Your task is to compute the expected value of (f(S)) modulo (998244353).

A convenient way to think about the problem is as follows. For a fixed set (S) of destination cities, we want to build a directed forest spanning all (n) nodes in which every tree has its root in (S) (i.e. for every vertex (v \notin S), we pick one incoming edge so that there is a unique path from (v) to its tree’s root). The overall cost is the sum of the costs of the selected edges, and we wish to choose the edges so that the total cost is minimized. Then the answer to the problem is the average value of (f(S)) when (S) is chosen uniformly at random among all (\binom{n}{k}) possible (k)-subsets of ({1,2,\dots,n}).

Note that in order to avoid fractional outputs, you need to output (f(S))'s expected value multiplied by the modular inverse of (\binom{n}{k}) modulo (998244353). All formulas are given in (\LaTeX) format.

inputFormat

The first line contains three integers (n), (m) and (k) (the number of cities, roads, and destination cities respectively). Each of the following (m) lines contains three integers (u_i), (v_i) and (w_i) indicating there is a directed road from city (u_i) to city (v_i) with cost (w_i). It is guaranteed that (w_i) is a positive integer.

outputFormat

Output a single integer: the expected minimum construction cost modulo (998244353).

sample

2 2 1
1 2 3
2 1 4

499122180