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

小 S 现在拥有 $n$ 座城市，第 $i$ 座城市的人口为 wiw_iw​i​​，城市与城市之间可能有双向道路相连。

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

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

定义第 $i$ 个州的满意度为：第 $i$ 个州的人口在前 $i$ 个州的人口中所占比例的 $p$ 次幂，即：

(∑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=1​i​​∑​x∈V​j​​​​w​x​​​​∑​x∈V​i​​​​w​x​​​​)​p​​

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

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

答案对 $998244353$ 取模。

两个划分 $\{V_1\dots V_k\}$ 和 $\{C_1\dots C_s\}$ 是不同的，当且仅当 $k\ne s$，或存在某个 $1\le i\le k$，使得 Vi≠CiV_i \neq C_iV​i​​≠C​i​​。

输入格式

从标准输入中读入数据。

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

接下来 $m$ 行，每行两个整数 $u,v$，描述一条无向的道路，保证无重边无自环；

输入第 $m+2$ 行有 $n$ 个正整数，第 $i$ 个正整数表示 wiw_iw​i​​。

输出格式

输出到标准输出中。

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

即设答案化为最简分式后的形式为 ab\frac a b​b​​a​​，其中 $a$ 和 $b$ 互质。输出整数 $x$ 使得 $bx\equiv a\left(\mathrm{mod}998244353\right)$ 且 $0\le x<998244353$。可以证明这样的整数 $x$ 是唯一的。

样例

样例 1 输入

3 2 1
1 2
2 3
1 1 1

样例 1 输出

1

样例 2

见附加文件下的 walk/walk2.in 与 walk/walk2.ans。

数据范围与提示

提示

$x^{p-1}\equiv 1\left(\mathrm{mod}p\right)$，其中 $p$ 为质数，$x\in \left[1,p\right)$。

子任务

保证对于所有数据有：$0\le n\le 21$，0≤m≤n(n−1)20 \leq m \leq \frac {n(n-1)} 20≤m≤​2​​n(n−1)​​，$0\le p\le 2$，1≤wi≤1001 \leq w_i \leq 1001≤w​i​​≤100。

测试点	每个测试点分值	$n$	$p$
1	$10$	$5$	$2$
2	$10$	$10$	$2$
3	$10$	$15$	$0$
4	$10$	$15$	$1$
5	$10$	$15$	$2$
6 ~ 9	$5$	$21$	$0$
10 ~ 13	$5$	$21$	$1$
14 ~ 15	$5$	$21$	$2$