问题陈述

给定一个由 $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。

输出在上述 $K$ 次动作期间 Takahashi 接收到的总金额的期望值，取模 $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