„Mam dość oglądania wciąż tych samych widoków na świecie” — Filozof Pang.

Świat Panga można uprościć do grafu skierowanego $G$ o $n$ wierzchołkach i $m$ krawędziach.

Ścieżka w $G$ to uporządkowana lista wierzchołków $(v_0, \dots, v_{t-1})$ dla pewnej nieujemnej liczby całkowitej $t$, taka że $v_i v_{i+1}$ jest krawędzią w $G$ dla wszystkich $0 \le i < t - 1$. W tym zadaniu ścieżka może być pusta.

Cykl w $G$ to uporządkowana lista różnych wierzchołków $(v_0, \dots, v_{t-1})$ dla pewnej dodatniej liczby całkowitej $t \ge 2$, taka że $v_i v_{(i+1) \pmod t}$ jest krawędzią w $G$ dla wszystkich $0 \le i < t$. Wszystkie przesunięcia cykliczne cyklu uznaje się za ten sam cykl.

Graf $G$ spełnia następującą własność: każdy wierzchołek należy do co najwyżej jednego cyklu.

Dla ustalonej liczby całkowitej $k$, oblicz liczbę par $(P_1, P_2)$ modulo 998244353 takich, że:

1. $P_1, P_2$ są ścieżkami;
2. Dla każdego wierzchołka $v \in G$, $v$ znajduje się w $P_1$ lub $P_2$;
3. Niech $c(P, v)$ oznacza liczbę wystąpień wierzchołka $v$ w ścieżce $P$. Dla każdego wierzchołka $v$ grafu $G$ zachodzi $c(P_1, v) + c(P_2, v) \le k$.

Wejście

Pierwsza linia zawiera 3 liczby całkowite $n, m$ oraz $k$ ($1 \le n \le 2000, 0 \le m \le 4000, 0 \le k \le 1000000000$).

Każda z kolejnych $m$ linii zawiera dwie liczby całkowite $a$ oraz $b$, oznaczające krawędź z wierzchołka $a$ do $b$ ($1 \le a, b \le n, a \neq b$).

Żadne dwie krawędzie nie łączą tej samej pary wierzchołków w tym samym kierunku.

Wyjście

Wypisz jedną liczbę całkowitą — liczbę par $(P_1, P_2)$ modulo 998244353.

Przykład

Wejście 1

2 2 1
1 2
2 1

Wyjście 1

6

Wejście 2

2 2 2
1 2
2 1

Wyjście 2

30

Wejście 3

3 3 3
1 2
2 1
1 3

Wyjście 3

103