Background

Little Z cannot stand trees, so he always wants to randomly add some edges to a tree. He thinks bipartite graphs are very harmonious, so he wants to know how many ways there are to turn a tree into a bipartite graph. Can you answer his query?

Problem Description

For an undirected rooted tree, define $f(i,k)$ as the number of ways, within the subtree rooted at $i$, to add $k$ edges inside it so that this subtree becomes a bipartite graph. Note that when adding edges, it is allowed to add an edge parallel to an original tree edge, but any two newly added edges must not be identical.

Given an undirected rooted tree with $n$ nodes, where the root is node $1$. For each $i \in [1,n]$, compute $f(i,k) \bmod p_i$.

Input Format

The input has $n+1$ lines.

Line $1$ contains two integers $n$ and $k$, representing the number of nodes in the tree and the parameter $k$.

Lines $2$ to $n$ each contain two positive integers, representing an edge between nodes $u_i$ and $v_i$.

Line $n+1$ contains $n$ integers, representing the modulus $p_i$ for each query.

Output Format

Output one line containing $n$ integers, each being the answer for the corresponding query.

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

9 0 1 0 1 0

Hint

[Sample 1 Explanation]

In this tree, adding edges $(u,v)\in\{(1,3),(1,5),(1,6),(2,3),(2,5),(2,6),(3,4),(4,5),(4,6)\}$ can make the tree bipartite.

[Constraints]

This problem uses bundled testdata.

For $100\%$ of the testdata: $1 \le n \le 5 \times 10^5$, $1 \le k \le 20$, $1 \le u_i, v_i \le n$, $2 \le p_i \le 2 \times 10^9$, and $p_i$ is a prime. There are at most $99$ distinct values of $p_i$. It is guaranteed that $p_i > k$.

• $\text{Special A}$: it is guaranteed that $k = 1$.
• $\text{Special B}$: it is guaranteed that $v_i = u_i + 1$.

[Hint]

The amount of I/O in this problem is large, so please use a faster I/O method.

Translated by ChatGPT 5