Arbore4

arbore4

== include(page="template/taskheader" task_id="arbore4") ==

Mitruţ are primele $N$ numere naturale nenule şi un arbore cu rădăcină cu $N$ noduri. El se întreabă în câte feluri poate plasa cele $N$ numere în nodurile arborelui, astfel încât fiecare nod să conţină un număr mai mic decât toate numerele din fiii săi.
 
h2. Cerinţă
 
Scrieţi un program care să răspundă la întrebarea lui Mitruţ prin afişarea numărului de modalităţi distincte de plasare a numerelor în arbore conform metodei de mai sus, **modulo 666013**.

Poveste şi cerinţă...

h2. Date de intrare

Fişierul $arbore4.in$ conţine pe prima linie numărul $N$ cu semnificaţia din enunţ. Următoarele $N–1$ linii vor conţine fiecare câte două numere întregi $x$ şi $y$, cu semnificaţia că există muchie între nodurile $x$ şi $y$.

Fişierul de intrare $arbore4.in$ ...

h2. Date de ieşire

Fişierul $arbore4.out$ va conţine un singur număr reprezentând răspunsul la întrebarea lui Mitruţ, **modulo 666013**.

În fişierul de ieşire $arbore4.out$ ...

h2. Restricţii si precizări

h2. Restricţii

* $1 ≤ N ≤ 100 000$
* Pentru $70%$ din teste $N ≤ 2 000$
* Rădăcina arborelui este nodul $1$
* Pentru $10%$ din teste $N ≤ 7$
* Arborele dat nu este neapărat binar (un nod poate avea mai mult de doi fii)

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. arbore4.in |_. arbore4.out |

| 5
 1 2
 3 1
 2 4
 2 5
| 8

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|
h3. Explicaţie

Modurile în care putem plasa numerele în nodurile arborelui dat sunt:
 
!problema/arbore4?arbore4.JPEG 70%!

...

== include(page="template/taskfooter" task_id="arbore4") ==

5542