L. Travel
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

"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 \lt 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 \lt 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$$$.
Input

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

Output one integer — the number of pairs $$$(P_1,P_2)$$$ modulo $$$998244353$$$.

Examples
Input
2 2 1
1 2
2 1
Output
6
Input
2 2 2
1 2
2 1
Output
30
Input
3 3 3
1 2
2 1
1 3
Output
103