Travel

"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,\ldots,v_{t-1})$ for some non-negative integer $t$ such that $v_iv_{i+1}$ is an edge in $G$ for all $0\le i<t-1$. A path can be empty.

A cycle in $G$ is an ordered list of distinct vertices $(v_0,\ldots,v_{t-1})$ for some integer $t \geq 2$ such that $v_iv_{(i+1) \bmod t}$ is an edge in $G$ for all $0\le 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:

1. $P_1$ and $P_2$ are paths.
2. For every vertex $v\in G$, $v$ is in $P_1$ or $P_2$.
3. Let $c(P,v)$ be the number of occurrences of $v$ in path $P$. For every vertex $v$ of $G$, $c(P_1,v)+c(P_2,v)\le k$.

The time limit is 2500 ms and the memory limit is 256 MB.

The first line contains three integers $n$, $m$, and $k$ ($1\le n\le 2000$, $0\le m\le 4000$, $0\le k\le 1000000000$).

Each of the next $m$ lines contains two integers $a$ and $b$, denoting an edge from vertex $a$ to vertex $b$ ($1\le a,b\le n$, $a\neq 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$.