arbsumpow

Arbsumpow

== include(page="template/taskheader" task_id="arbsumpow") ==

Poveste şi cerinţă...

Municipiul B. a fost numit de curând staţiune turistică de interes naţional - astfel a decis să înceapă să desemneze anumite zone din oraş ca fiind centre culturale. Oraşul este format din $N$ intersecţii, numerotate de la $1$ la $N$, legate printre ele cu $N - 1$ drumuri, astfel încât oricare două intersecţii să fie legate direct sau indirect prin drumuri. Fiecare intersecţie are câte o valoare culturală, intersecţia $i$ având valoarea $v[i]$.
 
Oraşul poate desemna o mulţime $S$ de intersecţii ca fiind centru cultural dacă şi numai dacă poţi ajunge din oricare intersecţie din $S$ la oricare alta trecând doar prin intersecţii din $S$ şi drumuri. Fie $M$ mulţimea de mulţimi $S$ ce pot fi desemnate ca centre culturale.
 
Pentru oricare mulţime de intersecţii $S ∈ M$, se consideră că valoarea culturală a centrului este dată de $v(S)$, definit prin <tex> v(S) = \left( \sum_{x \in S} v[x]\right)^P, </tex> pentru o constantă $P$.
 
Municipiul va desemna fiecare mulţime din $M$ ca fiind centru cultural pentru câte o zi, într-o ordine oarecare. Primăria este curioasă despre suma valorilor culturale a tuturor centrelor desemnate, modulo $10^9^+7$, adică <tex>\left( \sum_{S \in M} v(S) \right) \mod 10^9 + 7. </tex>
 
Îi puteţi ajuta să găsească această valoare?

h2. Date de intrare

Fişierul de intrare $arbsumpow.in$ ...

În prima linie a fişierului de intrare $arbsumpow.in$ se vor găsi valorile $N, P$. Urmează pe a doua linie valorile $v&lbrack;1&rbrack;, ..., v[N]$. Pe cea de-a treia linie se vor găsi valorile $p&lbrack;2&rbrack;, ... ,  p[N]$, indicând că există pentru fiecare $i$ de la $2$ la $N$ un drum între intersecţiile $i$ şi $p[i]$. Se garantează ca $p[i] < i$ oricare ar fi $1 < i &le; N$.

h2. Date de ieşire

În fişierul de ieşire $arbsumpow.out$ ...

În fişierul de ieşire $arbsumpow.out$ se va afişa o singură linie, ce conţine răspunsul cerut.

h2. Restricţii

* $... ≤ ... ≤ ...$
 
h2. Exemplu
 
table(example). |_. arbsumpow.in |_. arbsumpow.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

table(example). |_. Subtask |_. Punctaj |_. Restricţii |
| 1 | 7 | $1 ≤ N ≤ 15$, $1 ≤ v[i] ≤ 10^9^$, $1 ≤ P ≤ 7$ |
| 2 | 12 | $1 ≤ N ≤ 100$, $v[1] = ... = v[N] = 1$, $1 ≤ P ≤ 7$ |
| 3 | 5 | $1 ≤ N ≤ 1 000$, $v[1] = ... = v[N] = 1$, $1 ≤ P ≤ 7$ |
| 4 | 8 | $1 ≤ N ≤ 1 000$, $1 ≤ v[i] ≤ 10^9^$, $P = 1$ |
| 5 | 10 | $1 ≤ N ≤ 100 000$, $1 ≤ v[i] ≤ 10^9^$, $P = 1$ |
| 6 | 9 | $1 ≤ N ≤ 1 000$, $1 ≤ v[i] ≤ 10^9^$, $P = 2$ |
| 7 | 13 | $1 ≤ N ≤ 100 000$, $1 ≤ v[i] ≤ 10^9^$, $P = 2$ |
| 8 | 14 | $1 ≤ N ≤ 100 000$, $1 ≤ v[i] ≤ 10^9^$, $1 ≤ P ≤ 7$, o intersecţie e capătul a cel mult două drumuri |
| 9 | 22 | $1 ≤ N ≤ 100 000$, $1 ≤ v[i] ≤ 10^9^$, $1 ≤ P ≤ 7$ |
 
h2. Exemple
 
table(example). |_. arbsumpow.in |_. arbsumpow.out |
| 3 2
1 2 3
1 1
| 75 |
| 4 1
9 10 9 10
1 2 1
| 190 |
| 5 2
1 2 3 4 5
1 1 3 3
| 1133 |
| 7 2
1 1 1 1 1 1 1
1 1 1 2 5 2
| 590 |
| 10 3
13 8 4 8 6 13 6 8 14 9
1 2 3 3 2 6 5 4 8
| 12312296 |

h3. Explicaţie

h2. Explicaţie

...

Pentru primul exemplu, muchiile sunt $(1, 2)$, $(1, 3)$. Subarborii sunt determinaţi de următoarele mulţimi de noduri: ${1}, {2}, {3}, {1, 2}, {1, 3}, {1, 2, 3}$. Acestea au sumele $1, 2, 3, 3, 4, 6$. Ridicând acestea la pătrat ne dă $1, 4, 9, 9, 16, 36$, iar însumând ne dă $75$.

== include(page="template/taskfooter" task_id="arbsumpow") ==