随机游走到百万富翁

题目描述

给定一个由 $N$ 个顶点和 $M$ 条边组成的连通简单无向图。

对于 $i = 1, 2, \ldots, M$,第 $i$ 条边连接顶点 $u_i$ 和顶点 $v_i$。

高桥从 Level $0$ 开始,位于顶点 $1$,接下来将恰好执行 $K$ 次以下操作。

首先,从与当前所在顶点相邻的顶点中等概率随机选择一个并移动到该顶点。

然后,根据移动到的顶点 $v$ 发生以下事件。

• 如果 $C_v = 0$:高桥的 Level 增加 $1$。
• 如果 $C_v = 1$:高桥获得 $X^2$ 日元,其中 $X$ 是他当前的 Level。

输出上述 $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$

输出格式

输出答案。

样例

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

89349064

在高桥可能走过的多条路径中,考虑他从顶点 $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

数据范围

• $2 \le N \le 3000$
• $N-1 \le M \le \min\lbrace N(N-1)/2, 3000\rbrace$
• $1 \le K \le 3000$
• $1 \le u_i, v_i \le 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$
• 输入中的所有值均为整数。

提示

可以证明所求期望值总是有理数。另外,在本问题的数据范围下,当该值用两个互质的整数 $P$ 和 $Q$ 表示为 $\frac{P}{Q}$ 时,还可以证明存在唯一的整数 $R$,使得 $R \times Q \equiv P\pmod{998244353}$ 且 $0 \le R \lt 998244353$。请找出这个 $R$。