题目描述

茂密的森林中，小路交错纵横，一共有 $n$ 个岔路口，第 $i$ 个岔路口有美丽度 $a_i$，这些岔路口由 $m$ 条可以双向通行的道路所连接，第 $i$ 条道路连接岔路口 $u_i$ 和 $v_i$，不存在两条或多条道路连接相同的两个岔路口。

接下来 $n$ 天，由于雨季的来临，这些岔路口会不断的被积水所淹没，一个岔路口如果被积水淹没，那么这个路口以及与其相连接的路都不能通行，第 $i$ 天被淹没的岔路口的编号为 $p_i$。

由于不能通行的道路的存在，森林被分成了若干个连通块，橘猫们对于连通块的美丽度有独特的见解：

• 若连通块的形态是一棵树，其美丽度为块内所有岔路口的美丽度之和。
• 若连通块的形态不是树，其美丽度为 $1$。

在任意一天，整个森林的美丽度是所有连通块的美丽度的乘积。

整个雨季的美丽度是从第 $0$ 天（没有任何一个岔路口被淹没）到第 $n-1$ 天森林的美丽度之和。

橘猫们盼望着在雨季看到美景，请你帮她们求出对于所有可能的排列 $p_{1 \sim n}$，对应的雨季的美丽度之和是多少？

由于森林可能会非常美丽，你只需要输出美丽度 $\bmod 998244353$ 的值即可。

输入格式

第一行两个整数 $n$ 和 $m$，表示岔路口的数量和道路的数量。

第二行 $n$ 个整数，表示每个岔路口的美丽度。

第 $3 \sim m+2$ 行，每行两个整数 $u_i$ 和 $v_i$，表示第 $i$ 条道路两端的岔路口编号。

输出格式

输出一行一个整数，表示所有可能的排列所对应雨季的美丽度之和。

输入输出样例

输入 #1

3 3
1 2 3
1 2
2 3
3 1

输出 #1

42

输入 #2

4 5
1 2 3 4
1 3
2 4
2 3
3 4
1 4

输出 #2

290

说明/提示

样例 #1

该组样例满足子任务 1 的限制。

样例 #2

该组样例满足子任务 1 的限制。

样例 #3

见下发的 ex_forest3.in/.out。

该组样例满足子任务 1 的限制。

样例 #4

见下发的 ex_forest4.in/.out。

该组样例满足子任务 2 的限制。

样例 #5

见下发的 ex_forest5.in/.out。

该组样例满足子任务 3 的限制。

样例 #6

见下发的 ex_forest6.in/.out。

该组样例满足子任务 4 的限制。

样例 #7

见下发的 ex_forest7.in/.out。

该组样例满足子任务 5 的限制。

数据范围

对于所有测试数据，满足 $1 \leq n \leq 23$，$0 \leq m \leq \frac {n(n-1)}{2}$，$0 \leq a_i < 998244353$，$u_i \not= v_i$。

子任务编号	分值	限制	特殊性质
$1$	$20$	$n \le 9$	无
$2$	$10$	无	$\text{A}$
$3$	$15$	$n \leq 17$	无
$4$		$n \leq 20$
$5$	$40$	无

特殊性质 $\text{A}$：最初的图是一个森林。