시간 제한메모리 제한제출정답맞힌 사람정답 비율
2.5 초 (추가 시간 없음) 256 MB111100.000%

## 문제

"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$.

## 예제 입력 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