23462번 - 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 in this problem.

A cycle in $G$ is an ordered list of distinct vertices $(v_0,\ldots,v_{t-1})$ for some positive 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,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 first line contains $3$ 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 $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$.