1s 256M

题目描述

$\textit{Pang}$ 的世界可以简化为一个有向图 $G$，包含 $n$ 个顶点和 $m$ 条边。

在 $G$ 中，一条 $\textit{路径}$ 是一个有序顶点序列 $(v_0,\ldots,v_{t-1})$，其中 $t$ 是某个非负整数，满足对于所有 $0\le i<t-1$，$v_iv_{i+1}$ 是 $G$ 的一条边。在本题中，路径可以为空。

在 $G$ 中，一个 $\textit{环}$ 是一个由不同顶点组成的有序序列 $(v_0,\ldots,v_{t-1})$，其中 $t$ 是某个满足 $t\geq 2$ 的正整数，且对于所有 $0\le i<t$，$v_iv_{(i+1) \bmod t}$ 是 $G$ 的一条边。所有环的循环移位视为同一个环。

$G$ 满足如下性质：每个顶点至多属于一个环。

给定一个固定整数 $k$，请计算满足以下条件的有序对 $(P_1,P_2)$ 的数量，对 $998244353$ 取模：

• $P_1,P_2$ 都是路径；
• 对于 $G$ 的每个顶点 $v$，$v$ 必须出现在 $P_1$ 或 $P_2$ 中；
• 记 $c(P, v)$ 为顶点 $v$ 在路径 $P$ 中出现的次数。对于 $G$ 的每个顶点 $v$，有 $c(P_1,v)+c(P_2, v)\le k$。

输入格式

第一行包含 $3$ 个整数 $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$）。

没有两条边连接同一对顶点且方向相同。

输出格式

输出一个整数，表示满足条件的有序对 $(P_1,P_2)$ 的数量，对 $998244353$ 取模。

输入输出样例 #1

输入 #1

2 2 1
1 2
2 1

输出 #1

6

输入输出样例 #2

输入 #2

2 2 2
1 2
2 1

输出 #2

30

输入输出样例 #3

输入 #3

3 3 3
1 2
2 1
1 3

输出 #3

103

说明/提示

由 ChatGPT 4.1 翻译