頂点 $1$ を根とする $n$ 頂点の木を考えます。木内の各頂点 $i$ には重み $p_i$ があり、$p_1, p_2, \dots, p_n$ は順列をなします。
$L_{u,v}$ を頂点 $u$ から頂点 $v$ への単純パス上($u$ と $v$ を含む)にある任意の頂点の重みの最大値とします。$\operatorname{subtree}(i)$ を頂点 $i$ の部分木を構成する頂点の集合とします。$S_i = \{u \mid u \in \operatorname{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$ で割った余りを出力してください。
入力
1 行目には、木の頂点数を表す 1 つの整数 $n$ ($1 \le n \le 700$) が与えられます。
次の行には、$q_1, q_2, \dots, q_n$ ($0 \le q_i < 10^9 + 7$) を表す $n$ 個の整数が与えられます。
続く $n - 1$ 行には、それぞれ木の辺を表す 2 つの整数 $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