{"raw_statement":[{"iden":"statement","content":"\"I'm tired of seeing the same scenery in the world.\" — _Philosopher Pang_\n\n_Pang_'s world can be simplified as a directed graph $G$ with $n$ vertices and $m$ edges.\n\nA _path_ in $G$ is an ordered list of vertices $(v_0, \\\\dots, v_{t -1})$ for some non-negative integer $t$ such that $v_i v_{i + 1}$ is an edge in $G$ for all $0 <= i < t -1$. A _path_ can be empty in this problem.\n\nA _cycle_ in $G$ is an ordered list of distinct vertices $(v_0, \\\\dots, v_{t -1})$ for some positive integer $t >= 2$ such that $v_i v_{(i + 1} bmod t)$ is an edge in $G$ for all $0 <= i < t$. All circular shifts of a cycle are considered the same.\n\n$G$ satisfies the following property: Every vertex is in at most one cycle.\n\n Given a fixed integer $k$, count the number of pairs $(P_1, P_2)$ modulo $998244353$ such that \n\nThe first line contains $3$ integers $n$, $m$ and $k$ ($1 <= n <= 2000, 0 <= m <= 4000, 0 <= k <= 1000000000$).\n\nEach of the next $m$ lines contains two integers $a$ and $b$, denoting an edge from vertex $a$ to $b$ ($1 <= a, b <= n, a eq.not b$). \n\nNo two edges connect the same pair of vertices in the same direction.\n\nOutput one integer — the number of pairs $(P_1, P_2)$ modulo $998244353$.\n\n"},{"iden":"input","content":"The first line contains $3$ integers $n$, $m$ and $k$ ($1 <= n <= 2000, 0 <= m <= 4000, 0 <= k <= 1000000000$).Each of the next $m$ lines contains two integers $a$ and $b$, denoting an edge from vertex $a$ to $b$ ($1 <= a, b <= n, a eq.not b$). No two edges connect the same pair of vertices in the same direction."},{"iden":"output","content":"Output one integer — the number of pairs $(P_1, P_2)$ modulo $998244353$."},{"iden":"examples","content":"Input2 2 1\n1 2\n2 1\nOutput6\nInput2 2 2\n1 2\n2 1\nOutput30\nInput3 3 3\n1 2\n2 1\n1 3\nOutput103\n"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ G = (V, E) $ be a directed graph with $ |V| = n $, $ |E| = m $, where each vertex belongs to at most one directed cycle.  \nLet $ \\mathcal{P} $ be the set of all directed paths in $ G $ (including the empty path).  \nLet $ \\mathcal{C} $ be the set of all directed cycles in $ G $, where cycles are considered up to circular shift.  \n\n**Constraints**  \n1. $ 1 \\le n \\le 2000 $, $ 0 \\le m \\le 4000 $, $ 0 \\le k \\le 10^9 $  \n2. No multiple edges; $ a \\ne b $ for each edge $ (a,b) \\in E $  \n3. Each vertex is in at most one cycle.  \n\n**Objective**  \nCount the number of pairs $ (P_1, P_2) \\in \\mathcal{P} \\times \\mathcal{P} $ such that the total number of vertices covered by $ P_1 \\cup P_2 $ is exactly $ k $, modulo $ 998244353 $.  \n\nThat is:  \n$$\n\\left| \\left\\{ (P_1, P_2) \\in \\mathcal{P}^2 \\;\\middle|\\; \\left| V(P_1) \\cup V(P_2) \\right| = k \\right\\} \\right| \\mod 998244353\n$$","simple_statement":"Count the number of pairs of paths $(P_1, P_2)$ such that the total number of edges in both paths is exactly $k$, in a directed graph where each vertex belongs to at most one cycle.","has_page_source":false}