portocal

Ana a primit un arbore cu N noduri cu rădăcina în nodul 1, unde fiecare nod are asociată o valoare naturală de la 1 la M. Pentru fiecare nod, va scrie câte un șir format din valorile nodurilor de pe lanțul de la rădăcină la acel nod, în ordine. Apoi, va sorta cele N șiruri lexicografic.

După ce a obținut șirurile sortate, Ana se gândește la un șir S format din K numere naturale cuprinse, de asemenea, între 1 și M, și îl întreabă pe Portocal dacă există cel puțin un șir egal cu S. Cum Portocal este un motan leneș, el va verifica în fiecare zi un singur șir, începând cu primul în ordinea sortării, până când va găsi unul egal cu S.

Portocal a observat că unele noduri din arbore nu au încă asociată o valoare, așa că și-a propus să dea el valori acestor noduri (tot între 1 și M) înainte ca Ana să se apuce de scris șirurile. Scopul lui este să găsească șirul S cât mai repede. Pentru a decide cum să completeze valorile din arbore, are nevoie de răspunsul la două întrebări:

1. Numărul minim de zile în care Portocal poate găsi șirul S
2. Numărul de moduri în care poate completa valorile lipsă din arbore astfel încât să obțină acel număr minim de zile. Cum acest număr poate fi foarte mare, se mulțumește cu restul împărțirii la 1 000 000 009

Evident, Portocal își dorește să găsească cel puțin un șir egal cu S. Se garantează că există cel puțin o modalitate de a completa valorile arborelui pentru a realiza acest lucru.

Date de intrare

Prima linie va conține un număr C. Dacă C = 1, trebuie răspuns la întrebarea 1, iar dacă C = 2, trebuie răspuns la întrebarea 2. Pe a doua linie se vor afla numerele N, M și K. Pe a treia linie se găsesc N numere naturale $val_1, ... , val_N$ , reprezentând valorile asociate nodurilor din arbore. Dacă $val_i$ este −1, înseamnă că nodul i nu are încă asociată o valoare. Pe a patra linie se vor afla K numere naturale reprezentând șirul S. Următoarele N − 1 linii vor conține câte două numere u și v, reprezentând muchiile arborelui.

Date de ieșire

Se va afișa un singur număr reprezentând răspunsul la prima, respectiv a doua întrebare, în funcție de valoarea lui C.

Restricții

• C ∈ {1, 2}
• 1 ≤ K ≤ N ≤ 500 000
• 1 ≤ M ≤ 500 000
• $1 ≤ val_i ≤ M$ sau $val_i = −1$, oricare 1 ≤ i ≤ N
• $1 ≤ S_i ≤ M$, oricare 1 ≤ i ≤ K

Subtask 1 (8 puncte)

• C = 1, N ≤ 13, M ≤ 3

Subtask 2 (19 puncte)

• C = 1, N ≤ 5 000

Subtask 3 (22 puncte)

• C = 1

Subtask 4 (11 puncte)

• C = 2, N ≤ 13, M ≤ 3

Subtask 5 (40 puncte)

• C = 2

Exemple

stdin

1
8 3 3
-1 -1 2 -1 -1 -1 1 2
1 2 2
1 2
2 3
2 4
4 5
1 6
6 7
1 8

stdout

4

Explicații

Portocal poate completa valorile nodurilor astfel: 1 2 2 2 1 3 1 2.

Primele șiruri în ordine lexicografică vor fi:
1 - pentru nodul 1
1 2 - pentru nodul 2
1 2 - pentru nodul 8
1 2 2 - pentru nodul 3, care este egal cu S.
Astfel, răspunsul este 4.

Observați că, deși mai există un șir egal cu S, pentru nodul 4, Portocal se oprește când îl va găsi pe primul.

stdin

2
8 3 3
-1 -1 2 -1 -1 -1 1 2
1 2 2
1 2
2 3
2 4
4 5
1 6
6 7
1 8

stdout

6 

Explicații

Există 6 moduri de a completa valorile din arbore astfel încât Portocal să găsească șirul S în ziua 4. Acestea sunt:
1 2 2 2 1 3 1 2
1 2 2 3 1 3 1 2
1 2 2 2 2 3 1 2
1 2 2 3 2 3 1 2
1 2 2 2 3 3 1 2
1 2 2 3 3 3 1 2