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 10007.
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 sti, dri 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
0 < N ≤ 100 000
1 ≤ R ≤ N
1 ≤ K ≤ 100
Se acordă 40 de puncte pentru teste cu N≤100 şi K≤10.
Se acordă 60 de puncte pentru teste cu N≤400 şi K≤15.
