Rezolvare PBinfo #2971

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 trei 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ă două etape de prelungire a frunzelor.

Cerința

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

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 două numere întregi x și y cu semnificația că în arborele dat inițial există muchia [x, y].

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.

Restricții și precizări

• 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.
• 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;
• În concurs s-au acordat 10 puncte din oficiu. Aici se acordă pentru exemplele din enunț.

Exemplul 1:

tairos.in

4
3
1 2
3 1
3 4

tairos.out

5

Explicație

Arborele dat în fișierul de intrare are 4 noduri. Se cere numărul nodurilor aflate la distanța 3 față de rădăcină.
Urmărind imaginile din exemplele de mai sus,la distanța 3 avem următoarele 5 noduri: 222, 223, 241, 421 și 43.

Exemplul 2:

tairos.in

5
3
1 2
3 1
3 5
4 3

tairos.out

8

Exemplul 3:

tairos.in

5
25
2 1
2 3
1 4
5 2

tairos.out

33554432