P13949 [EC Final 2019] Travel

"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

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