여행

"세상에서 같은 풍경을 보는 것이 지겹다." --- 철학자 팡

팡의 세계는 정점 $n$개와 간선 $m$개로 이루어진 방향 그래프 $G$로 단순화할 수 있다.

$G$의 경로는 어떤 음이 아닌 정수 $t$에 대해 정점들을 순서대로 나열한 $(v_0,\ldots,v_{t-1})$이며, 모든 $0\le i<t-1$에 대해 $v_iv_{i+1}$이 $G$의 간선이다. 경로는 비어 있을 수 있다.

$G$의 사이클은 $t \geq 2$인 어떤 정수 $t$에 대해 서로 다른 정점들을 순서대로 나열한 $(v_0,\ldots,v_{t-1})$이며, 모든 $0\le i<t$에 대해 $v_iv_{(i+1) \bmod t}$가 간선이다. 사이클의 원형 이동은 모두 같은 사이클로 본다.

$G$는 다음 성질을 만족한다. 모든 정점은 최대 하나의 사이클에 속한다.

고정된 정수 $k$가 주어진다. 다음 조건을 모두 만족하는 쌍 $(P_1,P_2)$의 개수를 $998244353$으로 나눈 나머지를 구하라.

1. $P_1$, $P_2$는 경로이다.
2. $G$의 모든 정점 $v$는 $P_1$ 또는 $P_2$에 포함된다.
3. $c(P,v)$를 경로 $P$에서 $v`가 나타나는 횟수라 하자.$G$의 모든 정점$v$에 대해$c(P_1,v)+c(P_2,v)\le k$이다.

시간 제한은 2500 ms, 메모리 제한은 256 MB이다.

첫 줄에 정수 $n$, $m$, $k$가 주어진다 ($1\le n\le 2000$, $0\le m\le 4000$, $0\le k\le 1000000000$).

다음 $m$개의 줄에는 정점 $a$에서 정점 $b$로 가는 간선을 나타내는 정수 $a$, $b$가 주어진다 ($1\le a,b\le n$, $a\neq b$). 같은 방향의 간선이 두 번 주어지지 않는다.

답을 $998244353$으로 나눈 나머지를 정수 하나로 출력하라.