問題文

$N$ 頂点の木が与えられます。

木の頂点 $i$ には整数 $a_i$ が書かれています。

木の $j$ 番目の辺は頂点 $u_j$ と頂点 $v_j$ を結んでいます。

$1 \le k \le N$ なる整数 $k$ に対して、次の問題を解いてください。

• 頂点 $1$ から頂点 $k$ までの最短パス上の頂点に書かれている整数すべての最小公倍数を $10^9 + 7$ で割ったあまりを求めよ。

制約

• $1 \le N \le 2\times10^3$
• $1 \le a_i \le 10^9$
• $1 \le u_j, v_j \le N$
• $u_j \ne v_j$
• 与えられるグラフは木である
• 入力はすべて整数である

入力

出力

$N$ 行出力せよ。

$i$ 行目には、頂点 $1$ から頂点 $i$ までの最短パス上の最小公倍数を出力せよ。

入出力例

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

1
2
6
4
10
6
28
8

例えば、頂点 $1$ から $7$ までの最短パス上の頂点に書かれている整数は $1, 2, 4, 7$ です。 これらの最小公倍数は $28$ になります。

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

1
2
10
30
60
30
210
3
6
12

6
23 31 47 51 67 71
1 2
2 3
3 4
4 5
5 6

23
713
33511
1709061
114507087
130003121

答えは $10^9 + 7$ で割ったあまりであることに注意してください。