1362: #2340. 「WC2018」州区划分

Memory Limit:1024 MB Time Limit:10.000 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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

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

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

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

(∑x∈Viwx∑j=1i∑x∈Vjwx)p\left( \frac {\sum_{x \in V_i} w_x} {\sum_{j=1}^i \sum_{x \in V_j} w_x} \right)^p(j=1ixVjwxxViwx)p

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

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

答案对 998244353998244353998244353 取模。

两个划分 {V1Vk}{C1Cs} 是不同的,当且仅当 k≠sk \neq sks,或存在某个 1≤i≤k1 \leq i \leq k1ik,使得 Vi≠CiV_i \neq C_iViCi

输入格式

从标准输入中读入数据。

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

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

输入第 m+2m+2m+2 行有 nnn 个正整数,第 iii 个正整数表示 wiw_iwi

输出格式

输出到标准输出中。

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

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

样例

样例 1 输入

3 2 1
1 2
2 3
1 1 1

样例 1 输出

1

样例 2

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

数据范围与提示

提示

xp11(modp),其中 ppp 为质数,x∈[1,p)x \in \left[1, p\right)x[1,p)

子任务

保证对于所有数据有:0≤n≤210 \leq n \leq 210n210≤m≤n(n−1)20 \leq m \leq \frac {n(n-1)} 20m2n(n1)0≤p≤20 \leq p \leq 20p21≤wi≤1001 \leq w_i \leq 1001wi100

测试点 每个测试点分值 nnn ppp
1 101010 555 222
2 101010 101010 222
3 101010 151515 000
4 101010 151515 111
5 101010 151515 222
6 ~ 9 555 212121 000
10 ~ 13 555 212121 111
14 ~ 15 555 212121 222