题目背景

小 Z 看不惯树，所以他总想在树上随机添加一些边。他认为二分图是很和谐的，所以他想知道将一棵树变为二分图的方案数。你能否回答他的询问？

题目描述

对于一颗无向有根树，定义 $f(i,k)$ 表示在以 $i$ 为根的子树中，在其内部连 $k$ 条边，使得这颗子树变为一个二分图的方案数。请注意，加边时允许与原树边重边，但任意两条新加的边都不能重合。

给定一棵 $n$ 个点的无向有根树，根节点为 $1$ 号点。对于每个 $i\in [1,n]$，求 $f(i,k)$ 对 $p_i$ 取模的值。

输入格式

输入共 $n+1$ 行。

第 $1$ 行 $2$ 个整数，分别表示树的点数 $n$ 和参数 $k$。

接下来，第 $2$ 至 $n$ 行，每行 $2$ 个正整数，分别表示一条边连接的两个点的编号 $u_i$ 与 $v_i$。

第 $n+1$ 行 $n$ 个整数，分别表示每次询问时的模数 $p_i$。

输出格式

输出共 $1$ 行 $n$ 个整数，分别表示每次询问的答案。

6 1
1 3
1 5
1 6
2 5
3 4
998244353 998244353 998244353 998244353 998244353 998244353

9 0 1 0 1 0

提示

【样例 1 解释】

在这棵树上，连接 $(u,v)\in\{(1,3),(1,5),(1,6),(2,3),(2,5),(2,6),(3,4),(4,5),(4,6)\}$ 即可使树变为二分图。

【数据范围】

本题开启捆绑测试。

对于 $100\%$ 的数据，$1\le n\le5\times10^5$，$1\le k\le 20$，$1\le u_i,v_i\le n$，$2\le p_i\le2\times10^9$，$p_i$ 为素数。最多有 $99$ 个大小不同的 $p_i$。保证 $p_i>k$。

• $\text{Special A}$：保证 $k=1$；
• $\text{Special B}$：保证 $v_i=u_i+1$。

【提示】

本题 IO 量较大，请使用较快速的 IO 方式。