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 翻译