acolor

Omida-agent Smith s-a săturat să tot distrugă arborii şi acum îşi dezvoltă simţul artistic – îi place mult mai mult să-i coloreze.
De fiecare dată când vrea să creeze o nouă arbo-pictură îşi ia cu el cele K creioane colorate, îşi alege un arbore din grădină şi porneşte la lucru.
Arborele ales de Smith este alcătuit din $N$ noduri, are ca rădacină nodul $R$ şi o formă potrivită pentru pictură:

• fiecare nod are cel mult două crengi care duc spre două noduri: unul la stânga şi/sau unul la dreapta;
• între oricare două noduri există un drum unic format din crengi distincte, pe care omida se poate plimba pentru a ajunge de la un nod la celălalt;
• nodurile din subarborele stâng al unui nod sunt toate plasate mai la stânga decât acesta, iar cele din subarborele drept sunt toate mai la dreapta, de aceea nodurile au fost etichetate de la $1$ la $N$ de la cel mai din stânga până la cel mai din dreapta.

Omida a observat că picturile sale sunt frumoase doar dacă respectă unele reguli de bază pe care le-a citit într-o carte:

• orice nod trebuie să fie colorat cu exact una dintre cele $K$ colori;
• un nod trebuie să fie colorat diferit faţă de părintele dinspre rădăcină (adică faţă de nodul care precedă nodul respectiv atunci când omida se plimbă pe drumul de la rădăcină la nod);
• privit din exterior arborele trebuie să fie colorat diferit de la stânga la dreapta: orice nod are o culoare diferită de cel mai apropiat nod la stânga de el şi faţă de cel mai apropiat nod la dreapta (cu alte cuvinte culoarea nodului etichetat cu $i$ trebuie să fie diferită de culoarea nodurilor etichetate cu $i-1$, $i+1$).

Cerinţă

Scrieţi un program care să determine pentru un arbore dat în câte picturi frumoase (picturi care să respecte criteriile din enunţ) poate fi transformat acesta. Deoarece numărul cerut poate fi foarte mare, este suficient să aflaţi restul împărţirii la $10 \ 007$.

Date de intrare

Fişierul de intrare acolor.in va conţine pe prima linie numerele întregi $N$, $R$, $K$ separate prin câte un spaţiu. Pe următoarele $N$ linii este descrisă structura arborelui. Mai exact, pe linia $i+1$ vor exista două numere $st_i$, $dr_i$ separate printr-un spaţiu, reprezentând nodul fiu spre stânga şi respectiv nodul fiu spre dreapta al nodului $i$. Dacă un nod nu are fiu spre stânga şi/sau fiu spre dreapta atunci numărul corespunzător va fi $0$.

Date de ieşire

Fişierul de ieşire acolor.out va conţine o singură linie pe care va fi scris numărul de picturi frumoase care se pot obţine pentru arborele dat.

Restricţii şi precizări

• $0 < N \leq 100 \ 000$;
• $1 \leq R \leq N$;
• $1 \leq K \leq 100$;
• Se acordă $40$ de puncte pentru teste cu $N \leq 100$ şi $K \leq 10$.
• Se acordă $60$ de puncte pentru teste cu $N \leq 400$ şi $K \leq 15$.

Exemplul 1

acolor.in

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

acolor.out

3601

Explicație

Exemplul 2

acolor.in

3 1 2
0 3
0 0
2 0

acolor.out

0