#2340. 「WC2018」州区划分

内存限制:1024 MiB 时间限制:10000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Snakes

题目描述

小 S 现在拥有 nn 座城市,第 ii 座城市的人口为 wiw_i,城市与城市之间可能有双向道路相连。

现在小 S 要将这 nn 座城市划分成若干个州,每个州由至少一个城市组成,每个城市在恰好一个州内。

假设小 S 将这些城市划分成了 kk 个州,设 ViV_i 是第 ii 个州包含的所有城市所组成的集合。定义一条道路是一个州的内部道路,当且仅当这条道路的两个端点城市都在这个州内。如果一个州内部存在一条起点终点相同,不经过任何不属于这个州的城市,且经过这个州的所有内部道路都恰好一次并且经过这个州的所有城市至少一次的路径(路径长度可以为 00),则称这个州是不合法的。

定义第 ii 个州的满意度为:第 ii 个州的人口在前 ii 个州的人口中所占比例的 pp 次幂,即:

(xViwxj=1ixVjwx)p\left( \frac {\sum_{x \in V_i} w_x} {\sum_{j=1}^i \sum_{x \in V_j} w_x} \right)^p

定义一个划分的满意度为所有州的满意度的乘积

求所有合法的划分方案的满意度之和。

答案对 998244353998244353 取模。

两个划分 {V1Vk}\{V_1 \dots V_k\}{C1Cs}\{C_1 \dots C_s\} 是不同的,当且仅当 ksk \neq s,或存在某个 1ik1 \leq i \leq k,使得 ViCiV_i \neq C_i

输入格式

从标准输入中读入数据。

输入第一行包含三个整数 n,m,pn, m, p,表示城市个数、城市之间的道路个数以及题目描述中的常数 pp

接下来 mm 行,每行两个整数 u,vu, v,描述一条无向的道路,保证无重边无自环;

输入第 m+2m+2 行有 nn 个正整数,第 ii 个正整数表示 wiw_i

输出格式

输出到标准输出中。

输出一行一个整数表示答案在模 998244353998244353 意义下的取值。

即设答案化为最简分式后的形式为 ab\frac a b,其中 aabb 互质。输出整数 xx 使得 bxa(mod998244353)bx \equiv a \pmod {998244353}0x<9982443530 \leq x < 998244353。可以证明这样的整数 xx 是唯一的。

样例

样例 1 输入

3 2 1
1 2
2 3
1 1 1

样例 1 输出

1

样例 2

见附加文件下的 walk/walk2.inwalk/walk2.ans

数据范围与提示

提示

xp11(modp)x^{p-1} \equiv 1 \pmod p,其中 pp 为质数,x[1,p)x \in \left[1, p\right)

子任务

保证对于所有数据有:0n210 \leq n \leq 210mn(n1)20 \leq m \leq \frac {n(n-1)} 20p20 \leq p \leq 21wi1001 \leq w_i \leq 100

测试点 每个测试点分值 nn pp
1 1010 55 22
2 1010 1010 22
3 1010 1515 00
4 1010 1515 11
5 1010 1515 22
6 ~ 9 55 2121 00
10 ~ 13 55 2121 11
14 ~ 15 55 2121 22