102776: [AtCoder]ABC277 G - Random Walk to Millionaire

Problem Statement

You are given a connected simple undirected graph consisting of $N$ vertices and $M$ edges.
For $i = 1, 2, \ldots, M$, the $i$-th edge connects vertex $u_i$ and vertex $v_i$.

Takahashi starts at Level $0$ on vertex $1$, and will perform the following action exactly $K$ times.

• First, choose one of the vertices adjacent to the vertex he is currently on, uniformly at random, and move to the chosen vertex.
• Then, the following happens according to the vertex $v$ he has moved to.
  • If $C_v = 0$: Takahashi's Level increases by $1$.
  • If $C_v = 1$: Takahashi receives a money of $X^2$ yen, where $X$ is his current Level.

Print the expected value of the total amount of money Takahashi receives during the $K$ actions above, modulo $998244353$ (see Notes).

Notes

It can be proved that the sought expected value is always a rational number. Additionally, under the Constraints of this problem, when that value is represented as $\frac{P}{Q}$ using two coprime integers $P$ and $Q$, it can also be proved that there is a unique integer $R$ such that $R \times Q \equiv P\pmod{998244353}$ and $0 \leq R \lt 998244353$. Find this $R$.

Constraints

• $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$
• The given graph is connected.
• $C_i \in \lbrace 0, 1\rbrace$
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

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

Output

Print the answer.

Sample Input 1

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

Sample Output 1

89349064

Among the multiple paths that Takahashi may traverse, let us take a case where Takahashi starts on vertex $1$ and goes along the path $1 \rightarrow 2 \rightarrow 4 \rightarrow 5 \rightarrow 4 \rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow 3$, and compute the total amount of money he receives.

1. In the first action, he moves from vertex $1$ to an adjacent vertex, vertex $2$. Then, since $C_2 = 0$, his Level increases to $1$.
2. In the second action, he moves from vertex $2$ to an adjacent vertex, vertex $4$. Then, since $C_4 = 1$, he receives $1^2 = 1$ yen.
3. In the third action, he moves from vertex $4$ to an adjacent vertex, vertex $5$. Then, since $C_5 = 0$, his Level increases to $2$.
4. In the fourth action, he moves from vertex $5$ to an adjacent vertex, vertex $4$. Then, since $C_4 = 1$, he receives $2^2 = 4$ yen.
5. In the fifth action, he moves from vertex $4$ to an adjacent vertex, vertex $2$. Then, since $C_2 = 0$, his Level increases to $3$.
6. In the sixth action, he moves from vertex $2$ to an adjacent vertex, vertex $1$. Then, since $C_1 = 0$, his Level increases to $4$.
7. In the seventh action, he moves from vertex $1$ to an adjacent vertex, vertex $2$. Then, since $C_2 = 0$, his Level increases to $5$.
8. In the eighth action, he moves from vertex $2$ to an adjacent vertex, vertex $3$. Then, since $C_3 = 1$, he receives $5^2 = 25$ yen.

Thus, he receives a total of $1 + 4 + 25 = 30$ yen.

Sample Input 2

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

Sample Output 2

139119094

问题描述

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

Takahashi 在顶点 1 处从 Level $0$ 开始，将在接下来的 $K$ 次行动中执行以下操作。

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

求 Takahashi 在上述 $K$ 次行动中收到的总金钱的期望值，模$998244353$（见注意事项）。

注意事项

可以证明所求期望值始终是一个有理数。此外，在本问题的约束条件下，当该值表示为$\frac{P}{Q}$，使用两个互质的整数$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$

输出

输出答案。

样例输入 1

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

样例输出 1

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$ 日元。

样例输入 2

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

样例输出 2

139119094