G - 随机行走变百万富翁

评分：$600$ 分

问题描述

给定一个由 $N$ 个点和 $M$ 条边组成的连通简单无向图。
对于 $i = 1, 2, \ldots, M$，第 $i$ 条边连接了节点 $u_i$ 和节点 $v_i$。

高橋从第 $1$ 个点的 Level $0$ 开始，将执行以下动作 $K$ 次。

• 首先，均匀随机选择一个与当前所在节点相邻的点，并移动到选择的点上。
• 然后，根据他移动到的节点 $v$ 发生以下情况。
  • 如果 $C_v = 0$：高橋的 Level 值增加 $1$。
  • 如果 $C_v = 1$：高橋收到 $X^2$ 日元的金额，其中 $X$ 是他的当前 Level 值。

输出高橋在上述 $K$ 次动作中收到的总金额的期望值，模 $998244353$（参见注释）。

注释

可以证明所寻找的期望值始终是一个有理数。此外，在这个问题的约束条件下，当该值表示为用两个互质整数 $P$ 和 $Q$ 表示的 $\frac{P}{Q}$ 时，可以证明存在一个唯一的整数 $R$，满足 $R \times Q \equiv P \pmod{998244353}$ 且 $0 \leq R \lt 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$
• 输入中的所有值都是整数。

输入

从标准输入中按以下格式给出：

$N$ $M$ $K$

$u_1$ $v_1$

$u_2$ $v_2$

$\vdots$

$u_M$ $v_M$

$C_1$ $C_2$ $\ldots$ $C_N$

输出

输出答案。

5 4 8
4 5
2 3
2 4
1 2
0 0 1 1 0

89349064

在 Takahashi 可能经过的多个路径中，让我们假设 Takahashi 从节点 $1$ 开始，沿着路径 $1 \rightarrow 2 \rightarrow 4 \rightarrow 5 \rightarrow 4 \rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow 3$ ，并计算他收到的总金额。

1. 在第一个动作中，他从节点 $1$ 移动到一个相邻的节点，节点 $2$。然后，由于 $C_2 = 0$，他的 Level 值增加到 $1$。
2. 在第二个动作中，他从节点 $2$ 移动到一个相邻的节点，节点 $4$。然后，由于 $C_4 = 1$，他收到 $1^2 = 1$ 日元。
3. 在第三个动作中，他从节点 $4$ 移动到一个相邻的节点，节点 $5$。然后，由于 $C_5 = 0$，他的 Level 值增加到 $2$。
4. 在第四个动作中，他从节点 $5$ 移动到一个相邻的节点，节点 $4$。然后，由于 $C_4 = 1$，他收到 $2^2 = 4$ 日元。
5. 在第五个动作中，他从节点 $4$ 移动到一个相邻的节点，节点 $2$。然后，由于 $C_2 = 0$，他的 Level 值增加到 $3$。
6. 在第六个动作中，他从节点 $2$ 移动到一个相邻的节点，节点 $1$。然后，由于 $C_1 = 0$，他的 Level 值增加到 $4$。
7. 在第七个动作中，他从节点 $1$ 移动到一个相邻的节点，节点 $2$。然后，由于 $C_2 = 0$，他的 Level 值增加到 $5$。
8. 在第八个动作中，他从节点 $2$ 移动到一个相邻的节点，节点 $3$。然后，由于 $C_3 = 1$，他收到 $5^2 = 25$ 日元。

因此，他总共收到 $1 + 4 + 25 = 30$ 日元。

8 12 20
7 6
2 6
6 4
2 1
8 5
7 2
7 5
3 7
3 5
1 8
6 3
1 4
0 0 1 1 0 0 0 0

139119094