「私は世界の同じ景色を見るのに飽きてしまった。」 — 哲学者 Pang

Pang の世界は、$n$ 個の頂点と $m$ 個の辺を持つ有向グラフ $G$ として単純化できる。

$G$ におけるパスとは、ある非負整数 $t$ に対する頂点の順序付きリスト $(v_0, \dots, v_{t-1})$ であり、すべての $0 \le i < t - 1$ に対して $v_i v_{i+1}$ が $G$ の辺であるものを指す。本問において、パスは空であってもよい。

$G$ におけるサイクルとは、ある正整数 $t \ge 2$ に対する相異なる頂点の順序付きリスト $(v_0, \dots, v_{t-1})$ であり、すべての $0 \le i < t$ に対して $v_i v_{(i+1) \pmod t}$ が $G$ の辺であるものを指す。サイクルの巡回シフトはすべて同一とみなす。

$G$ は次の性質を満たす：すべての頂点は高々1つのサイクルに含まれる。

固定された整数 $k$ が与えられる。以下の条件を満たす組 $(P_1, P_2)$ の数を $998244353$ で割った余りを求めよ。

1. $P_1, P_2$ はパスである。
2. すべての頂点 $v \in G$ について、$v$ は $P_1$ または $P_2$ に含まれる。
3. $c(P, v)$ をパス $P$ における $v$ の出現回数とする。$G$ のすべての頂点 $v$ について、$c(P_1, v) + c(P_2, v) \le k$ が成り立つ。

入力

入力の最初の行には、3つの整数 $n, m, k$ ($1 \le n \le 2000, 0 \le m \le 4000, 0 \le k \le 1000000000$) が含まれる。 続く $m$ 行の各行には、頂点 $a$ から $b$ への辺を表す2つの整数 $a$ と $b$ ($1 \le a, b \le n, a \neq b$) が含まれる。 同じ方向に同じ頂点の組を結ぶ辺は2つ存在しない。

出力

組 $(P_1, P_2)$ の数を $998244353$ で割った余りを1つの整数として出力せよ。

入出力例

入力 1

2 2 1
1 2
2 1

出力 1

6

入力 2

2 2 2
1 2
2 1

出力 2

30

入力 3

3 3 3
1 2
2 1
1 3

出力 3

103