【WC2018】州区划分
小$S$现在拥有$n$座城市，第$i$座城市的人口为$w_i$，城市与城市之间可能有双向道路相连。
现在小$S$要将这$n$座城市划分成若干个州，每个州由至少一个城市组成，每个城市在恰好一个州内。
假设小$S$将这些城市划分成了$k$个州，设$V_i$是第$i$个州包含的所有城市组成的集合。 定义一条道路是一个州的内部道路，当且仅当这条道路的两个端点城市都在这个州内。 如果一个州内部存在一条起点终点相同，不经过任何不属于这个州的城市，且经过这个州的每个城市至少一次、所有内部道路都恰好一次的路径（路径长度可以为0），则称这个州是不合法的。
定义第$i$个州的满意度为：第$i$个州的人口在前$i$个州的人口中所占比例的$p$次幂，即：
$$\left (\frac{\sum_{x \in V_i}{w_x}}{\sum_{j=1}^{i}\sum_{x \in V_j}{w_x}}\right )^p$$
定义一个划分的满意度为所有州的满意度的乘积，求所有合法的划分方案的满意度之和，答案对$998244353$取模。
两个划分$\{V_1...V_k\}$和$\{C_1...C_s\}$是不同的，当且仅当$k\neq s$，或存在某个$1\leq i\leq k$，使得$V_i\neq C_i$。
输入格式
从标准输入读入数据。
输入第一行包含三个整数 $n,m,p$，表示城市个数、城市之间的道路个数以及题目描述中的常数$p$；
接下来$m$行，每行两个正整数$u,v$，描述一条无向的道路，保证无重边无自环；
输入第$m+2$行有$n$个正整数，第$i$个正整数表示$w_i$。
输出格式
输出到标准输出。
输出一行一个整数表示答案在模 $998244353$ 意义下的取值。
即设答案化为最简分式后的形式为 $\frac{a}{b}$ ，其中 $a$ 和 $b$ 互质。输出整数 $x$ 使得 $bx \equiv a \mod 998244353$ 且 $0 \leq x < 998244353$。可以证明这样的整数 $x$ 是唯一的。
3 2 1
1 2
2 3
1 1 1
1
提示
$x^{p-1} \equiv 1 \mod p$，其中 $p$ 为质数，$x \in [1,p)$。
限制与约定
保证对于所有数据有：$0\leq n\leq 21$，$0\leq m\leq \frac{n\times (n-1)}{2}$，$0\leq p\leq 2$，$1\leq w_i\leq 100$。
测试点 $1 \sim 5$：$n\le 15$，每个测试点 $10$ 分；
测试点 $7\sim 9$：$n\le 21, p = 0$，每个测试点 $5$ 分；
测试点 $10\sim 13$：$n\le 21, p = 1$，每个测试点 $5$ 分；
测试点 $14\sim 15$：$n\le 21, p = 2$，每个测试点 $5$ 分。
时间限制：$10\texttt{s}$
空间限制：$1\texttt{GB}$