小$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$ 是唯一的。

样例一

input

3 2 1
1 2
2 3
1 1 1

output

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}$

下载

样例数据下载