计数有向生成树（以 r 为根）

（Counting Spanning Trees (Directed)）

问题描述

给定一个有向图（可能含重边和自环），含 $N$ 个顶点和 $M$ 条边。第 $i$ 条边从顶点 $u_i$ 指向顶点 $v_i$。
另给定一个根顶点 $r$（$0 \le r < N$）。

求以 $r$ 为根的有向生成树（arborescence）的数量：即一个边集 $T$，满足：

• $|T| = N-1$；
• 图 $(V, T)$ 是一棵以 $r$ 为根的有向树（所有边指向远离根的方向，且每个非根顶点有且仅有一条入边，根无入边）；
• 所有顶点均可从 $r$ 到达。

结果对 $998244353$ 取模。

约束条件

• $1 \leq N \leq 500$
• $0 \leq M \leq 5 \times 10^5$
• $0 \leq r < N$
• $0 \leq u_i, v_i < N$

输入

$N\ M\ r$
$u_0\ v_0$
$u_1\ v_1$
:
$u_{M-1}\ v_{M-1}$

输出

以 $r$ 为根的有向生成树数量 $\bmod\ 998244353$

3 5 2
0 1
0 1
1 2
2 1
2 0

3

1 2 0
0 0
0 0

1

#3

4 4 3
0 1
1 0
2 3
3 2

0

4 8 2
0 1
0 3
2 1
3 1
3 0
3 0
2 3
1 3

8