“我厌倦了在这个世界上看同样的风景。” —— 哲学家 Pang

Pang 的世界可以简化为一个具有 $n$ 个顶点和 $m$ 条边的有向图 $G$。

$G$ 中的一条路径是一个顶点序列 $(v_0, \dots, v_{t-1})$，其中 $t$ 为某个非负整数，且对于所有 $0 \le i < t-1$，$(v_i, v_{i+1})$ 均为 $G$ 中的一条边。在本题中，路径可以为空。

$G$ 中的一个环是一个由不同顶点组成的序列 $(v_0, \dots, v_{t-1})$，其中 $t$ 为某个正整数且 $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$。

输入格式

第一行包含 3 个整数 $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