AT_abc277_g.[ABC277G] Random Walk to Millionaire

给定一个包含 $N$ 个顶点和 $M$ 条边的连通且简单的无向图。
对于 $i = 1, 2, \ldots, M$，第 $i$ 条边连接顶点 $u_i$ 和顶点 $v_i$。

高桥君一开始处于顶点 $1$，等级为 $0$，然后他会恰好进行 $K$ 次如下操作：

• 首先，从当前所在顶点的所有相邻顶点中，等概率随机选择一个顶点并移动到该顶点。
• 然后，根据移动后的顶点 $v$，会发生如下事件：
  • 如果 $C_v = 0$：高桥君的等级增加 $1$。
  • 如果 $C_v = 1$：设高桥君当前等级为 $X$，他会获得 $X^2$ 日元。

请输出在上述 $K$ 次操作过程中，高桥君获得的金钱总额的期望值，结果对 $998244353$ 取模（见注释）。

输入以如下格式从标准输入给出。

$N$ $M$ $K$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_M$ $v_M$
$C_1$ $C_2$ $\ldots$ $C_N$

请输出答案。

注释

可以证明，所求的期望值一定是有理数。在本题的约束下，设其为两个互质整数 $P$、$Q$ 的比值 $\frac{P}{Q}$，则存在唯一的整数 $R$ 满足 $R \times Q \equiv P \pmod{998244353}$ 且 $0 \leq R < 998244353$。请输出这个 $R$。

约束条件

• $2 \leq N \leq 3000$
• $N-1 \leq M \leq \min\lbrace N(N-1)/2,\ 3000\rbrace$
• $1 \leq K \leq 3000$
• $1 \leq u_i, v_i \leq N$
• $u_i \neq v_i$
• $i \neq j \implies \lbrace u_i, v_i\rbrace \neq \lbrace u_j, v_j\rbrace$
• 给定的图是连通的
• $C_i \in \lbrace 0, 1\rbrace$
• 输入均为整数

样例解释 1

高桥君的移动路径有多种可能，这里以 $1 \rightarrow 2 \rightarrow 4 \rightarrow 5 \rightarrow 4 \rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow 3$ 为例，计算他获得的金钱总额：

1. 第 1 次操作，从顶点 $1$ 移动到相邻的顶点 $2$。$C_2 = 0$，等级升为 $1$。
2. 第 2 次操作，从顶点 $2$ 移动到相邻的顶点 $4$。$C_4 = 1$，获得 $1^2 = 1$ 日元。
3. 第 3 次操作，从顶点 $4$ 移动到相邻的顶点 $5$。$C_5 = 0$，等级升为 $2$。
4. 第 4 次操作，从顶点 $5$ 移动到相邻的顶点 $4$。$C_4 = 1$，获得 $2^2 = 4$ 日元。
5. 第 5 次操作，从顶点 $4$ 移动到相邻的顶点 $2$。$C_2 = 0$，等级升为 $3$。
6. 第 6 次操作，从顶点 $2$ 移动到相邻的顶点 $1$。$C_1 = 0$，等级升为 $4$。
7. 第 7 次操作，从顶点 $1$ 移动到相邻的顶点 $2$。$C_2 = 0$，等级升为 $5$。
8. 第 8 次操作，从顶点 $2$ 移动到相邻的顶点 $3$。$C_3 = 1$，获得 $5^2 = 25$ 日元。

因此，高桥君获得的金钱总额为 $1 + 4 + 25 = 30$ 日元。

由 ChatGPT 4.1 翻译