Lítum á tré með $n$ hnútum, þar sem hnútur $1$ er rótin. Hver hnútur $i$ í trénu hefur þyngd $p_i$, þannig að $p_1, p_2, \dots, p_n$ er umröðun.
Látum $L_{u,v}$ tákna mestu þyngd nokkurs hnúts á einfalda veginum frá hnúti $u$ til hnúts $v$ ($u$ og $v$ meðtalin). Látum $\operatorname{subtree}(i)$ tákna mengi þeirra hnúta sem mynda undirtré hnúts $i$. Við skilgreinum $S_i = \{u \mid u \in \operatorname{subtree}(i) \land L_{u,i} \le p_i\}$, sem er mengi þeirra hnúta sem hægt er að komast til með því að byrja í $i$, færa sig eingöngu til barna og fara eingöngu í gegnum hnúta með þyngd minni en eða jafna $p_i$. Látum $f_i = |S_i|$, sem táknar stærð þessa hnútamengis.
Við skilgreinum gildi hnúts sem $q_{f_i}$, þar sem $q$ er gefin gildaruna $q_1, q_2, \dots, q_n$.
Nú viljum við reikna, fyrir hvert par $(i, j)$, summu gilda hnúts $i$ fyrir allar þyngdasamsetningar sem uppfylla $p_i = j$. Þar sem svarið getur verið mjög stórt, vinsamlegast prentið niðurstöðuna módúló $10^9 + 7$.
Inntak
Fyrsta línan inniheldur eina heiltölu $n$ ($1 \le n \le 700$), sem táknar fjölda hnúta í trénu.
Næsta lína inniheldur $n$ heiltölur, sem tákna $q_1, q_2, \dots, q_n$ ($0 \le q_i < 10^9 + 7$).
Næstu $n - 1$ línur innihalda hver um sig tvær heiltölur $u, v$, sem tákna legg í trénu.
Úttak
Prentið $n$ línur, þar sem hver lína inniheldur $n$ heiltölur. $i$-ta línan og $j$-ta heiltalan tákna samsvarandi svar módúló $10^9 + 7$.
Dæmi
Inntak 1
3 1 1 2 1 2 2 3
Úttak 1
2 2 4 2 2 2 2 2 2
Inntak 2
4 1 2 3 4 1 2 2 3 1 4
Úttak 2
6 10 16 24 6 8 10 12 6 6 6 6 6 6 6 6
Inntak 3
7 3 7 2 4 1 8 9 1 2 1 3 2 4 4 5 3 6 4 7
Úttak 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