"I'm tired of seeing the same scenery in the world." — _Philosopher Pang_
_Pang_'s world can be simplified as a directed graph $G$ with $n$ vertices and $m$ edges.
A _path_ in $G$ is an ordered list of vertices $(v_0, \\dots, v_{t -1})$ for some non-negative integer $t$ such that $v_i v_{i + 1}$ is an edge in $G$ for all $0 <= i < t -1$. A _path_ can be empty in this problem.
A _cycle_ in $G$ is an ordered list of distinct vertices $(v_0, \\dots, v_{t -1})$ for some positive integer $t >= 2$ such that $v_i v_{(i + 1} bmod t)$ is an edge in $G$ for all $0 <= i < t$. All circular shifts of a cycle are considered the same.
$G$ satisfies the following property: Every vertex is in at most one cycle.
Given a fixed integer $k$, count the number of pairs $(P_1, P_2)$ modulo $998244353$ such that
The first line contains $3$ integers $n$, $m$ and $k$ ($1 <= n <= 2000, 0 <= m <= 4000, 0 <= k <= 1000000000$).
Each of the next $m$ lines contains two integers $a$ and $b$, denoting an edge from vertex $a$ to $b$ ($1 <= a, b <= n, a eq.not b$).
No two edges connect the same pair of vertices in the same direction.
Output one integer — the number of pairs $(P_1, P_2)$ modulo $998244353$.
## Input
The first line contains $3$ integers $n$, $m$ and $k$ ($1 <= n <= 2000, 0 <= m <= 4000, 0 <= k <= 1000000000$).Each of the next $m$ lines contains two integers $a$ and $b$, denoting an edge from vertex $a$ to $b$ ($1 <= a, b <= n, a eq.not b$). No two edges connect the same pair of vertices in the same direction.
## Output
Output one integer — the number of pairs $(P_1, P_2)$ modulo $998244353$.
[samples]
**Definitions**
Let $ G = (V, E) $ be a directed graph with $ |V| = n $, $ |E| = m $, where each vertex belongs to at most one directed cycle.
Let $ \mathcal{P} $ be the set of all directed paths in $ G $ (including the empty path).
Let $ \mathcal{C} $ be the set of all directed cycles in $ G $, where cycles are considered up to circular shift.
**Constraints**
1. $ 1 \le n \le 2000 $, $ 0 \le m \le 4000 $, $ 0 \le k \le 10^9 $
2. No multiple edges; $ a \ne b $ for each edge $ (a,b) \in E $
3. Each vertex is in at most one cycle.
**Objective**
Count the number of pairs $ (P_1, P_2) \in \mathcal{P} \times \mathcal{P} $ such that the total number of vertices covered by $ P_1 \cup P_2 $ is exactly $ k $, modulo $ 998244353 $.
That is:
$$
\left| \left\{ (P_1, P_2) \in \mathcal{P}^2 \;\middle|\; \left| V(P_1) \cup V(P_2) \right| = k \right\} \right| \mod 998244353
$$