Tairos

tairos

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

Se dă un arbore cu $N$ noduri, numerotate de la $1$ la $N$.
Arborele se va transforma astfel: la oricare etapă fiecare nod de gradul $1$ diferit de rădăcină din arborele

Se dă un arbore cu N noduri, numerotate de la 1 la N.
Arborele se va transforma astfel: la oricare etapă fiecare nod de gradul 1 diferit de rădăcină din arborele

actual se înlocuieşte cu un arbore identic cu cel dat iniţial, iar la următoarea etapă procedeul se va relua

pentru arborele obţinut, formându-se astfel un arbore infinit. În următoarele $3$ imagini se prezintă un

pentru arborele obţinut, formându-se astfel un arbore infinit. În următoarele 3 imagini se prezintă un

exemplu de arbore dat iniţial, arborele obţinut după prima etapă de prelungire a frunzelor şi arborele

obţinut după $2$ etape de prelungire a frunzelor.

obţinut după 2 etape de prelungire a frunzelor.

!problema/tairos?Untitled2.jpg!

Să se determine câte noduri se află la distanţă $D$ de rădăcina arborelui infinit.

Să se determine câte noduri se află la distanţă D de rădăcina arborelui infinit.

h2. Date de intrare

Pe prima linie a fişierului de intrare tairos.in se va afla un număr natural $N$, reprezentând numărul de
noduri din arborele dat iniţial. Pe a doua linie se va afla numărul întreg $D$, cu semnificaţia de mai sus, iar
fiecare dintre următoarele $N-1$ linii conţine câte $2$ numere întregi $x$ şi $y$ cu semnificaţia că în arborele dat
iniţíal există muchia $[x,y]$.

Pe prima linie a fişierului de intrare tairos.in se va afla un număr natural N, reprezentând numărul de
noduri din arborele dat iniţial. Pe a doua linie se va afla numărul întreg D, cu semnificaţia de mai sus, iar
fiecare dintre următoarele N-1 linii conţine câte 2 numere întregi x şi y cu semnificaţia că în arborele dat
iniţíal există muchia [x,y].

h2. Date de ieşire
Fişierul de ieşire tairos.out va conţine un singur număr, şi anume restul împărţirii numărului de

noduri cerut la numărul $1.000.000.007$.

noduri cerut la numărul 1.000.000.007.

h2. Restricţii

* $2 ≤ N ≤ 100$
* $1 ≤ D ≤ 10.000$

* 2 ≤ N ≤ 100
* 1 ≤ D ≤ 10.000

* Un arbore este un graf neorientat, conex şi fără cicluri.

* Distanţa dintre două noduri $x$ şi $y$ ale unui arbore este egală cu numărul de muchii ale unui lanţ
cu extremităţile în nodurile $x$ şi $y$, lanţ format din noduri distincte.

* Distanţa dintre două noduri x şi y ale unui arbore este egală cu numărul de muchii ale unui lanţ
cu extremităţile în nodurile x şi y, lanţ format din noduri distincte.

* Rădăcina va fi considerată ca fiind nodul 1;

* Pentru teste în valoare de $17$ puncte avem $N = 3$
* Pentru teste în valoare de alte $22$ puncte răspunsul este $≤ 10 000$;

* Pentru teste în valoare de 17 puncte avem N = 3
* Pentru teste în valoare de alte 22 puncte răspunsul este ≤ 10 000;

h2. Exemplu