考慮一樖有 $n$ 個節點嘅樹,其中節點 $1$ 係根。樹入面嘅每個節點 $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$ 取模後嘅值。
輸入格式
第一行包含一個整數 $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