#P17741. 小A的魔法阵
小A的魔法阵
题目描述
小A是一个拥有古老血脉的魔法师,机缘巧合,他得到了一本魔法书。为了提升自己的能力,他学习魔法书,从书中的魔法阵提取魔力。
魔法阵上有个魔力节点,每一个魔力节点都有一个魔力值。有对魔力节点之间有着魔力连接。
小A每次会选择一个魔力节点的点集,点亮它们,并从中提取魔力。然而这样的仪式并不是一定可以成功。如果中有两个节点之间有魔法连接,就会导致魔法的不稳定,使仪式失败。如果有一个以外的节点,和中的节点全都没有魔法连接,就会导致魔力供应不足,使仪式失败。
一次成功的仪式,提取到的魔力是中每个点的魔力值之和乘以外每个点的魔力值之和,而一次失败的仪式提取不到魔力。
小A还对魔法阵的根源很感兴趣。他惊奇地发现,这个魔法阵是由个魔法石加以神奇的魔法变化而来的:先将个魔法石排好,每个魔法石都有魔法强度,魔法结束后,个魔法石会变成个魔力节点,两个魔力节点间有魔法连接当且仅当并且。
小A想知道对于所有不同仪式,可以提取到的魔力和为多少。两种仪式不同,当且仅当不同。
由于提取到的魔力和可能很大,小A只想知道它对998244353取模后的结果。
输入格式
从标准输入读入。
第一行读入,表示魔力节点数和魔法连接数。
第二行读入个正整数,表示魔力值。
接下来行,每行两个整数,表示之间有魔法连接。
输出格式
输出到标准输出。
输出一行一个整数,表示答案对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
subtask 2 5pts
subtask 3 31pts
subtask 4 15pts
subtask 5 20pts 没有特殊限制