「我厭倦了看世界上同樣的風景。」—— 哲學家 Pang

Pang 的世界可以簡化為一個具有 $n$ 個頂點和 $m$ 條邊的有向圖 $G$。

圖 $G$ 中的一條路徑（path）是一個頂點序列 $(v_0, \dots, v_{t-1})$，其中 $t$ 為某個非負整數，且對於所有 $0 \le i < t - 1$，$(v_i, v_{i+1})$ 均為 $G$ 中的一條邊。在本題中，路徑可以是空的。

圖 $G$ 中的一個環（cycle）是一個由相異頂點組成的序列 $(v_0, \dots, v_{t-1})$，其中 $t \ge 2$ 為某個正整數，且對於所有 $0 \le i < t$，$(v_i, v_{(i+1) \pmod t})$ 均為 $G$ 中的一條邊。環的所有循環移位被視為同一個環。

圖 $G$ 滿足以下性質：每個頂點至多屬於一個環。

給定一個固定的整數 $k$，請計算滿足以下條件的數對 $(P_1, P_2)$ 的數量，並對 998244353 取模：

1. $P_1, P_2$ 皆為路徑；
2. 對於圖 $G$ 中的每一個頂點 $v$，$v$ 必須出現在 $P_1$ 或 $P_2$ 中；
3. 令 $c(P, v)$ 為頂點 $v$ 在路徑 $P$ 中出現的次數。對於圖 $G$ 中的每一個頂點 $v$，滿足 $c(P_1, v) + c(P_2, v) \le k$。

輸入格式

第一行包含三個整數 $n, m$ 和 $k$ ($1 \le n \le 2000, 0 \le m \le 4000, 0 \le k \le 1000000000$)。

接下來 $m$ 行，每行包含兩個整數 $a$ 和 $b$，表示一條從頂點 $a$ 到 $b$ 的邊 ($1 \le a, b \le n, a \neq b$)。

沒有兩條邊連接同一對頂點且方向相同。

輸出格式

輸出一個整數，代表滿足條件的數對 $(P_1, P_2)$ 的數量，對 998244353 取模。

範例

輸入 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