Arbsumpow

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

$\displaystyle v(S) = \left(\sum_{x∈S} v[x]\right)^P$,

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ă

$\displaystyle \left(\sum_{S∈M} v(S)\right)$ mod $10^9 + 7$.

Îi puteți ajuta să găsească această valoare?

Date de intrare

În prima linie a fișierului de intrare se vor găsi valorile N, P. Urmează pe a doua linie valorile v[1], ... , v[N]. Pe cea de-a treia linie se vor găsi valorile p[2], ... , 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 ≤ N.

Date de ieșire

Se va afișa o singură linie, ce conține răspunsul cerut.

Restricții și precizări

Subtask 1 (7 puncte)

• 1 ≤ N ≤ 15
• $1 ≤ v[i] ≤ 10^9$
• 1 ≤ P ≤ 7

Subtask 2 (12 puncte)

• 1 ≤ N ≤ 100
• v[1] = ... = v[N] = 1
• 1 ≤ P ≤ 7

Subtask 3 (5 puncte)

• 1 ≤ N ≤ 1 000
• v[1] = ... = v[N] = 1
• 1 ≤ P ≤ 7

Subtask 4 (8 puncte)

• 1 ≤ N ≤ 1 000
• $1 ≤ v[i] ≤ 10^9$
• P = 1

Subtask 5 (10 puncte)

• 1 ≤ N ≤ 100 000
• $1 ≤ v[i] ≤ 10^9$
• P = 1

Subtask 6 (9 puncte)

• 1 ≤ N ≤ 1 000
• $1 ≤ v[i] ≤ 10^9$
• P = 2

Subtask 7 (13 puncte)

• 1 ≤ N ≤ 100 000
• $1 ≤ v[i] ≤ 10^9$
• P = 2

Subtask 8 (14 puncte)

• 1 ≤ N ≤ 100 000
• $1 ≤ v[i] ≤ 10^9$
• 1 ≤ P ≤ 7
• o intersecție e capătul a cel mult două drumuri

Subtask 9 (22 puncte)

• 1 ≤ N ≤ 100 000
• $1 ≤ v[i] ≤ 10^9$
• 1 ≤ P ≤ 7

Exemple

stdin

3 2
1 2 3
1 1

stdout

75

stdin

4 1
9 10 9 10
1 2 1

stdout

190

stdin

5 2
1 2 3 4 5
1 1 3 3

stdout

1133

stdin

7 2
1 1 1 1 1 1 1
1 1 1 2 5 2

stdout

590

stdin

10 3
13 8 4 8 6 13 6 8 14 9
1 2 3 3 2 6 5 4 8

stdout

12312296

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.