Betrachte einen Baum mit $n$ Knoten, wobei Knoten $1$ die Wurzel ist. Jeder Knoten $i$ im Baum hat ein Gewicht $p_i$, sodass $p_1, p_2, \dots, p_n$ eine Permutation bildet.
Sei $L_{u,v}$ das maximale Gewicht eines Knotens auf dem einfachen Pfad von Knoten $u$ zu Knoten $v$ (einschließlich $u$ und $v$). Sei $\operatorname{subtree}(i)$ die Menge der Knoten, die den Teilbaum von Knoten $i$ bilden. Wir definieren $S_i = \{u \mid u \in \operatorname{subtree}(i) \land L_{u,i} \le p_i\}$, also die Menge der Knoten, die ausgehend von $i$ erreicht werden können, wenn man sich nur zu Kindern bewegt und nur Knoten mit einem Gewicht kleiner oder gleich $p_i$ passiert. Sei $f_i = |S_i|$ die Größe dieser Knotenmenge.
Wir definieren den Wert eines Knotens als $q_{f_i}$, wobei $q$ eine gegebene Wertefolge $q_1, q_2, \dots, q_n$ ist.
Nun möchten wir für jedes Paar $(i, j)$ die Summe der Werte von Knoten $i$ über alle Gewichtskonfigurationen berechnen, die $p_i = j$ erfüllen. Da die Antwort sehr groß sein kann, gib das Ergebnis bitte modulo $10^9 + 7$ aus.
Eingabe
Die erste Zeile enthält eine ganze Zahl $n$ ($1 \le n \le 700$), welche die Anzahl der Knoten im Baum angibt.
Die nächste Zeile enthält $n$ ganze Zahlen, welche $q_1, q_2, \dots, q_n$ ($0 \le q_i < 10^9 + 7$) darstellen.
Die folgenden $n - 1$ Zeilen enthalten jeweils zwei ganze Zahlen $u, v$, die eine Kante im Baum darstellen.
Ausgabe
Gib $n$ Zeilen aus, die jeweils $n$ ganze Zahlen enthalten. Die $j$-te ganze Zahl in der $i$-ten Zeile stellt die entsprechende Antwort modulo $10^9 + 7$ dar.
Beispiele
Eingabe 1
3 1 1 2 1 2 2 3
Ausgabe 1
2 2 4 2 2 2 2 2 2
Eingabe 2
4 1 2 3 4 1 2 2 3 1 4
Ausgabe 2
6 10 16 24 6 8 10 12 6 6 6 6 6 6 6 6
Eingabe 3
7 3 7 2 4 1 8 9 1 2 1 3 2 4 4 5 3 6 4 7
Ausgabe 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