P11032 『DABOI Round 1』Develop a Tree

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

对于一颗无向有根树，定义 $f(i,k)$ 表示在以 $i$ 为根的子树中，在其内部连 $k$ 条边，使得这颗子树变为一个二分图的方案数。请注意，加边时允许与原树边重边，但任意两条新加的边都不能重合。 给定一棵 $n$ 个点的无向有根树，根节点为 $1$ 号点。对于每个 $i\in [1,n]$，求 $f(i,k)$ 对 $p_i$ 取模的值。

无

无

**【样例 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{Subtask}$ | $n\le$ | $\text{Special}$ | $\text{Score}$ | | :----------: | :----------: | :----------: | :----------: | | $1$ | $5\times10^5$ | $\text{A}$ | $10$ | | $2$ | $10^3$ | $\text{No}$ | $15$ | | $3$ | $5\times10^5$ | $\text{B}$ | $15$ | | $4$ | $5\times10^5$ | $\text{No}$ | $60$ | - $\text{Special A}$：保证 $k=1$； - $\text{Special B}$：保证 $v_i=u_i+1$。 --- **【提示】** 本题 IO 量较大，请使用较快速的 IO 方式。