«Мне надоело видеть одни и те же пейзажи в этом мире», — философ Панг.

Мир Панга можно упростить до ориентированного графа $G$ с $n$ вершинами и $m$ ребрами.

Путь в $G$ — это упорядоченный список вершин $(v_0, \dots, v_{t-1})$ для некоторого неотрицательного целого числа $t$, такой что $v_i v_{i+1}$ является ребром в $G$ для всех $0 \le i < t - 1$. В этой задаче путь может быть пустым.

Цикл в $G$ — это упорядоченный список различных вершин $(v_0, \dots, v_{t-1})$ для некоторого целого числа $t \ge 2$, такой что $v_i v_{(i+1) \pmod t}$ является ребром в $G$ для всех $0 \le i < t$. Все циклические сдвиги цикла считаются одинаковыми.

Граф $G$ обладает следующим свойством: каждая вершина принадлежит не более чем одному циклу.

Для заданного целого числа $k$ подсчитайте количество пар $(P_1, P_2)$ по модулю $998244353$, таких что:

1. $P_1, P_2$ — пути;
2. Для каждой вершины $v \in G$, $v$ входит в $P_1$ или $P_2$;
3. Пусть $c(P, v)$ — количество вхождений вершины $v$ в путь $P$. Для каждой вершины $v$ графа $G$ выполняется $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