WBTree

Cu toții știm ce este acela un ciur (adică o sită); putem folosi unul pentru a separa făina grunjoasă de cea fină. Cu toate acestea, în problema de față vom încerca să ciuruim nodurile unui arbore.

Nadgob Ciuruitorul are un arbore (graf neorientat conex aciclic) cu $N$ noduri. Nadgob vrea să aleagă o submulțime $S$ de noduri ale arborelui. Pentru a realiza această alegere, el se va așeza, pe rând, în $K$ noduri distincte ale arborelui. Odată așezat într-un nod $x$ al arborelui, el poate, de oricâte ori dorește, să selecteze un nod $y$ și să "ciuruiască" (adică să adauge la $S$) toate nodurile $z$ pentru care $y$ se află pe cel mai scurt drum dintre $x$ și $z$. Desigur, un nod care este deja în $S$ nu va fi adăugat din nou.

Nadgob se află acum într-o poziție de nelămurire existențială. Plin de angoasă, el se întreabă în câte moduri poate alege submulțimea $S$ conform procedurii enunțate anterior (modulo $10^9 + 7$). Două moduri sunt considerate distincte dacă submulțimile rezultate sunt distincte.

Protocol de interacțiune

Concurentul va implementa funcția solve, cu următoarea semnătură:

int solve (int N, std::vector<int> p, std::vector<int> q, std::vector<int> r);

Parametrii acestei funcții au următoarea semnificație::

• $N$ - numarul de noduri ale arborelui;
• $p, q$ - vectori de lungime $N - 1$ ce conțin capetele muchiilor arborelui (mai exact, există o muchie bidirecțională între nodurile $p[i]$ și $q[i]$, oricare ar fi $0 \le i < N$);
• $r$ - vector de lungime $K$ ce conține nodurile în care se va așeaza Nadgob, in ordine.

Funcția va întoarce rezultatul cerut în enuntul problemei. Concurentul NU va implementa o funcție main.

Restricții

• $1 \le K \le N \le 10^5$

Subtask 1 (4 puncte)

• $1 \le N \le K \le 20$

Subtask 2 (7 puncte)

• $1 \le N \le 20$

Subtask 3 (5 puncte)

• Arborele conține cel mult un nod de grad mai mare de $1$.

Subtask 4 (6 puncte)

• Arborele nu conține niciun nod de grad mai mare de $2$.

Subtask 5 (7 puncte)

• $K = 1$

Subtask 6 (7 puncte)

• $K = N$

Subtask 7 (20 puncte)

• $K = 2$

Subtask 8 (21 puncte)

• $1 \le N \le 10^3$

Subtask 9 (23 puncte)

• Restricții inițiale.

Exemple

Input

3 1
0 1
0 2
0

Output

5

Input

7 4
0 1
0 2
3 0
4 2
3 6
3 5
4 3 1 2

Output

39

Explicații

Pentru primul exemplu:

Nadgob se așează în nodul $0$.

• Selectând niciun $y$, rezultă $S = \emptyset$.
• Selectând $y = 0$, rezultă $S = \{0, 1, 2\}$.
• Selectând $y = 1$, rezultă $S = \{1\}$.
• Selectând $y = 2$, rezultă $S = \{2\}$.
• Selectând $y = 1$ și $y = 2$, rezultă $S = {1, 2}.

Pentru al doilea exemplu: