#P17741. 小A的魔法阵

小A的魔法阵

题目描述

小A是一个拥有古老血脉的魔法师,机缘巧合,他得到了一本魔法书。为了提升自己的能力,他学习魔法书,从书中的魔法阵提取魔力。

魔法阵上有nn个魔力节点,每一个魔力节点都有一个魔力值a1..ana_1..a_n。有mm对魔力节点之间有着魔力连接。

小A每次会选择一个魔力节点的点集SS,点亮它们,并从中提取魔力。然而这样的仪式并不是一定可以成功。如果SS中有两个节点之间有魔法连接,就会导致魔法的不稳定,使仪式失败。如果有一个SS以外的节点,和SS中的节点全都没有魔法连接,就会导致魔力供应不足,使仪式失败。

一次成功的仪式,提取到的魔力是SS中每个点的魔力值之和乘以SS外每个点的魔力值之和,而一次失败的仪式提取不到魔力。

小A还对魔法阵的根源很感兴趣。他惊奇地发现,这个魔法阵是由nn个魔法石加以神奇的魔法变化而来的:先将nn个魔法石排好,每个魔法石都有魔法强度h1..hnh_1..h_n,魔法结束后,nn个魔法石会变成nn个魔力节点,两个魔力节点i,ji,j间有魔法连接当且仅当i<ji<j并且hi>hjh_i>h_j。

小A想知道对于所有不同仪式,可以提取到的魔力和为多少。两种仪式不同,当且仅当SS不同。

由于提取到的魔力和可能很大,小A只想知道它对998244353取模后的结果。

输入格式

从标准输入读入。

第一行读入n,mn,m,表示魔力节点数和魔法连接数。

第二行读入nn个正整数a1..ana_1..a_n,表示魔力值。

接下来mm行,每行两个整数x,yx,y,表示x,yx,y之间有魔法连接。

输出格式

输出到标准输出。

输出一行一个整数,表示答案对998244353取模后的结果。

样例

样例输入 1

3 3
1 1 2
1 2
1 3
2 3

样例输出 1

10

样例解释

成功的仪式有:

1.点亮1,提取到3点魔力

2.点亮2,提取到3点魔力

3.点亮3,提取到4点魔力

3+3+4=10

数据范围

保证对于所有魔法阵都可以由至少一个魔法石序列构建出来。

$m\le \frac{n\times (n-1)}{2},1\le a_i\le 100,2\le n \le 1000$

subtask 1 29pts n≤20n\le 20

subtask 2 5pts m=n×(n−1)2m=\frac{n\times (n-1)}{2}

subtask 3 31pts n≤200n\le 200

subtask 4 15pts ai=1a_i=1

subtask 5 20pts 没有特殊限制