一种高传播性的细菌感染了一棵包含 $n$ 个节点的树（有 $n-1$ 条边，无环）。这些节点从 $1$ 到 $n$ 编号。

初始时恰好有一个节点会被感染。树上的每个节点都有一个初始易感权重 $a_i$，这意味着节点 $i$ 成为树的初始感染节点的概率为 $\frac{a_i}{\sum_{i=1}^n a_i}$。

此外，每个节点都有一个感染概率 $p_i$，表示它被相邻节点感染的概率。

具体来说，从初始感染节点开始，如果一个节点被感染，与其相邻的未感染节点 $x$ 将以 $p_x$ 的概率成为新的被感染节点，随后 $x$ 可以继续感染其相邻节点。

现在，你的任务是计算最终恰好有 $k$ 个节点被感染的概率。你需要对每个 $k = 1, \dots, n$ 输出一个答案。

你需要将答案对 $10^9 + 7$ 取模，这意味着如果你的答案是 $\frac{a}{b}$（且 $\gcd(a, b) = 1$），你需要输出 $a \cdot b^{-1} \pmod{10^9 + 7}$，其中 $b \cdot b^{-1} \equiv 1 \pmod{10^9 + 7}$。

输入格式

第一行包含一个整数 $n$ ($2 \le n \le 2\,000$)，表示树的节点数。

接下来的 $n-1$ 行，每行包含两个正整数 $u$ 和 $v$ ($1 \le u, v \le n$)，表示树上存在一条边 $(u, v)$。

接下来的 $n$ 行，第 $i$ 行包含三个正整数 $a_i, b_i, c_i$，其中 $a_i$ 的含义如上所述，且 $p_i = \frac{b_i}{c_i}$。

保证 $1 \le a_i, b_i, c_i \le 10^9$，$ \sum_{i=1}^n a_i \le 10^9$，$b_i \le c_i$，$\gcd(b_i, c_i) = 1$。

输出格式

输出 $n$ 行，每行包含一个整数。第 $i$ 行的整数应为 $k=i$ 时的答案对 $10^9 + 7$ 取模的结果。

样例

样例输入 1

5
2 1
5 2
3 2
4 3
2 1 5
3 1 2
2 1 1
2 1 1
3 1 2

样例输出 1

208333335
166666668
166666668
950000007
508333337