题目描述

有一棵 $n$ 个节点的树，你将从任意一个点出发开始随机游走。

具体来说，在点 $u$ 的每个单位时间内你将会有 $p_u$ 的概率留在原地，有 $1−p_u$ 的概率等概率的向相邻的点移动，直到移动到 $1$ 号点才停下。

现在询问从每个点出发直至停下，所花费的时间的 $k$ 次方的期望。

可以证明，答案可以被表示成 $q × p^{-1}$的形式，你需要输出一个非负整数 $ans$, 使得 $ans ≡ q × p^{−1}(\mod 998244353)$, 保证 $p$ 将不会是 $998244353$ 的倍数。

输入格式

第一行两个整数 $n$ 和 $k$, 含义如题目所示。

接下来 $n − 1$ 行，每行两个整数 $u, v$，代表一条树边。

接下来一行 $n − 1$ 个整数, 第 $i$ 个 $p^{'}_{i+1}$。$p_{i+1} =p^{'}_{i+1} × 10^{-6}$ 代表留在原地的概率。

输出格式

输出 $n − 1$ 行，第 $i$ 输出从 $i + 1$ 号点出发直至停下，所花费的时间的 $k$ 次方的期望。

样例

样例输入1

3 1
1 2
2 3
0 0

样例输出1

3
4

样例输入2

3 1
1 2
2 3
500000 500000

样例输出2

6
8

样例输入3

3 2
1 2
2 3
500000 500000

样例输出3

74
104

数据范围与提示

对于 $15\%$ 的数据，保证 $n \leq 10$, $k \leq 10$。

对于 $30\%$ 的数据，保证 $n \leq 50$, $k \leq 50$。

对于 $50\%$ 的数据，保证 $n \leq 1000$, $k \leq 100$。

对于另外 $5\%$ 的数据，保证 $k = 0$。

对于另外 $15\%$ 的数据，保证 $k = 1$。

对于另外 $10\%$ 的数据，保证 $p_i = 0$。

对于 $95\%$ 的数据，保证 $k \leq 1000$。

对于 $100\%$ 的数据，保证 $nk <= 10^6$, $1 \leq n \leq 10^5$,$0 \leq k \leq 10^5$, $0 \leq p_i < 10^6$。