Tinjau sebuah pohon dengan $n$ simpul, di mana simpul $1$ adalah akarnya. Setiap simpul $i$ pada pohon memiliki bobot $p_i$, sedemikian sehingga $p_1, p_2, \dots, p_n$ merupakan sebuah permutasi.
Misalkan $L_{u,v}$ menyatakan bobot maksimum dari simpul mana pun pada jalur sederhana dari simpul $u$ ke simpul $v$ (termasuk $u$ dan $v$). Misalkan $\operatorname{subtree}(i)$ menyatakan himpunan simpul yang membentuk upapohon dari simpul $i$. Kita definisikan $S_i = \{u \mid u \in \operatorname{subtree}(i) \land L_{u,i} \le p_i\}$, yaitu himpunan simpul yang dapat dicapai mulai dari $i$, hanya dengan bergerak ke simpul anak dan hanya melewati simpul-simpul dengan bobot kurang dari atau sama dengan $p_i$. Misalkan $f_i = |S_i|$, yang menyatakan ukuran dari himpunan simpul tersebut.
Kita definisikan nilai dari sebuah simpul sebagai $q_{f_i}$, di mana $q$ adalah barisan nilai yang diberikan $q_1, q_2, \dots, q_n$.
Sekarang kita ingin menghitung, untuk setiap pasangan $(i, j)$, jumlah nilai dari simpul $i$ untuk semua konfigurasi bobot yang memenuhi $p_i = j$. Karena jawabannya mungkin sangat besar, keluarkan hasilnya modulo $10^9 + 7$.
Masukan
Baris pertama berisi satu bilangan bulat $n$ ($1 \le n \le 700$), yang menyatakan jumlah simpul pada pohon.
Baris berikutnya berisi $n$ bilangan bulat, yang menyatakan $q_1, q_2, \dots, q_n$ ($0 \le q_i < 10^9 + 7$).
$n - 1$ baris berikutnya masing-masing berisi dua bilangan bulat $u, v$, yang menyatakan sebuah sisi pada pohon.
Keluaran
Keluarkan $n$ baris, masing-masing berisi $n$ bilangan bulat. Baris ke-$i$ dan bilangan bulat ke-$j$ menyatakan jawaban yang bersesuaian modulo $10^9 + 7$.
Contoh
Masukan 1
3 1 1 2 1 2 2 3
Keluaran 1
2 2 4 2 2 2 2 2 2
Masukan 2
4 1 2 3 4 1 2 2 3 1 4
Keluaran 2
6 10 16 24 6 8 10 12 6 6 6 6 6 6 6 6
Masukan 3
7 3 7 2 4 1 8 9 1 2 1 3 2 4 4 5 3 6 4 7
Keluaran 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