电路

题目描述

你正在使用 $N$ 个部件（编号为 $1$ 到 $N$）和 $M$ 根电缆制作一个电路。

这些部件总共有 $M$ 个红色端子和 $M$ 个蓝色端子，第 $i$ 个红色端子连接在部件 $R_i$ 上，第 $i$ 个蓝色端子连接在部件 $B_i$ 上。

每根电缆连接一个红色端子和一个蓝色端子。特别地，允许连接同一个部件上的两个端子。一个端子不能连接两根或更多电缆。因此，连接这 $M$ 根电缆总共有 $M!$ 种方式（电缆之间不区分）。

将这个电路视为以部件为顶点、电缆为边的图，设 $s$ 为该图的连通分量个数。

当从 $M!$ 种方式中随机选择连接方式时，求 $s$ 的期望值，对 $998244353$ 取模。

「对 $998244353$ 取模的期望值」是什么意思？

可以证明，所求期望值总是一个有理数。此外，在本问题的约束下，可以证明当该值用两个互质的整数 $P$ 和 $Q$ 表示为 $\frac{P}{Q}$ 时，恰好存在一个整数 $R$ 满足 $R \times Q \equiv P\pmod{998244353}$ 且 $0 \leq R \lt 998244353$。求这个 $R$。

输入格式

输入按以下格式从标准输入给出：

$N$ $M$
$R_1$ $R_2$ $\dots$ $R_M$
$B_1$ $B_2$ $\dots$ $B_M$

输出格式

输出 $s$ 的期望值对 $998244353$ 取模的结果。

样例

3 2
1 2
3 2

499122178

设 $(i, j)$ 表示将第 $i$ 个红色端子与第 $j$ 个蓝色端子用电缆连接。

对于 $(1,1), (2,2)$：会形成两个连通分量 $\lbrace 1,3 \rbrace$ 和 $\lbrace 2 \rbrace$，所以 $s=2$。

对于 $(1,2), (2,1)$：整个图构成一个连通分量，所以 $s=1$。

因此，$s$ 的期望值为 $\frac{3}{2} \equiv 499122178 \pmod {998244353}$。

17 5
1 1 1 1 1
1 1 1 1 1

17

无论怎样连接电缆，都有 $s=N$。

8 10
2 4 7 1 7 6 1 4 8 1
5 1 5 2 5 8 4 6 1 3

608849831

数据范围

• $1\leq N \leq 17$
• $1 \leq M \leq 10^5$
• $1 \leq R_i, B_i \leq N$
• 输入中的所有值均为整数。