题目描述

"I'm tired of seeing the same scenery in the world." --- $\textit{Philosopher Pang}$

$\textit{Pang}$'s world can be simplified as a directed graph $G$ with $n$ vertices and $m$ edges.

A $\textit{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 $\textit{path}$ can be empty in this problem.

A $\textit{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

• $P_1,P_2$ are paths;
• For every vertex $v\in G$, $v$ is in $P_1$ or $P_2$;
• 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$.

2 2 1
1 2
2 1

6

2 2 2
1 2
2 1

30

3 3 3
1 2
2 1
1 3

103