考虑一棵拥有 $n$ 个节点的树，其中节点 1 是根。树中的每个节点 $i$ 都有一个权重 $p_i$，使得 $p_1, p_2, \dots, p_n$ 是一个排列。

令 $L_{u,v}$ 表示从节点 $u$ 到节点 $v$ 的简单路径上（包括 $u$ 和 $v$）任意节点的最大权重。令 $subtree(i)$ 表示由节点 $i$ 的子树组成的节点集合。我们定义 $S_i = \{u | u \in subtree(i) \land L_{u,i} \le p_i\}$，即：从 $i$ 出发，仅向子节点移动且仅经过权重小于或等于 $p_i$ 的节点所能到达的节点集合。令 $f_i = |S_i|$，表示该集合的大小。

我们定义节点的值为 $q_{f_i}$，其中 $q$ 是给定的数值序列 $q_1, q_2, \dots, q_n$。

现在我们想要对于每一对 $(i, j)$，计算在所有满足 $p_i = j$ 的权重配置下，节点 $i$ 的值的总和。由于答案可能很大，请输出结果对 $10^9 + 7$ 取模后的值。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 700$)，表示树中节点的数量。

第二行包含 $n$ 个整数，表示 $q_1, q_2, \dots, q_n$ ($0 \le q_i < 10^9 + 7$)。

接下来的 $n - 1$ 行，每行包含两个整数 $u, v$，表示树中的一条边。

输出格式

输出 $n$ 行，每行包含 $n$ 个整数。第 $i$ 行的第 $j$ 个整数表示对应的答案对 $10^9 + 7$ 取模后的结果。

样例

样例输入 $1$

3
1 1 2
1 2
2 3

样例输出 $1$

2 2 4
2 2 2
2 2 2

样例输入 $2$

4
1 2 3 4
1 2
2 3
1 4

样例输出 $2$

6 10 16 24
6 8 10 12
6 6 6 6
6 6 6 6

样例输入 $3$

7
3 7 2 4 1 8 9
1 2
1 3
2 4
4 5
3 6
4 7

样例输出 $3$

2160 3120 3168 2952 2160 3720 6480
2160 2640 2640 2412 2208 2280 2880
2160 2640 3120 3600 4080 4560 5040
2160 3120 3648 3744 3408 2640 1440
2160 2160 2160 2160 2160 2160 2160
2160 2160 2160 2160 2160 2160 2160
2160 2160 2160 2160 2160 2160 2160