Fişierul intrare/ieşire:	manuscris.in, manuscris.out	Sursă	Baraj Shumen Seniori ICHB-Vianu - 2022
Autor	Livia Magureanu	Adăugată de	Comisie Seniori Vianu ICHB •comisie_baraj_shumen_ichb_vianu_seniori
Timp execuţie pe test	0.2 sec	Limită de memorie	262144 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Manuscris

• Ghoberscris = forma "scrisă" a limbii ghoberiene

• Limba ghoberiană = limba vorbită de ghoberieni

• Ghoberieni = locuitorii țării Ghobera

În această problemă ne interesează în mod special analizarea unor propoziții din limba ghoberiană. Ghoberscrisul este un scris deosebit de impractic și nu a supraviețuit până în zilele noastre întrucât doar fetele puteau diferenția atâtea culori.
În primul rând, în ghoberscris, cuvintele nu sunt reprezentate prin semne grafice, ci prin culori (ghoberienii dispuneau de foarte multe culori).
În al doilea rând, topica propoziției este irelevantă pentru înțelesul acesteia. Sensul propoziției este determinat strict de cuvintele care o compun și de conexiunile dintre ele. Prin urmare, o propoziție scrisă în ghoberscris are forma unui arbore în care fiecare nod reprezintă un cuvânt (în funcție de culoarea acestuia).

Din păcate, manuscrisele care s-au păstrat au fost deteriorate de timp și culorile de pe ele au ajuns indescifrabile, însă structura propoziției s-a păstrat.
Dându-se structura unei propoziții (sub formă de arbore) și numărul k de cuvinte / culori distincte din limba ghoberiană, calculați numărul de înțelesuri distincte pe care le putea avea inițial propoziția.

Două înțelesuri se consideră ghober-diferite dacă nu există o renumerotare a nodurilor astfel încât să se obțină doi arbori colorați identic.

Mai exact: Doi arbori G(V, E, c: V -> C) și G'(V, E', c': V -> C) se considera "la fel" (izomorfi) dacă există o funcție f: V -> V' bijectivă a.î. c'(f(v)) = c(v) oricare ar fi v ∈ V si E' = {(f(v), f(u)) | (v, u) ∈ E} unde C = {1, 2 ... k} și V = {1, 2 ... n}.

Date de intrare

Fişierul de intrare manuscris.in conține pe prima linie două numere, n și k, reprezentând numărul de cuvinte din propoziția dată și respectiv numărul de cuvinte / culori din limba ghoberiană. Pe următoarele n - 1 linii se vor afla câte două numere, a și b cu semnificația că există o conexiune între cuvintele a și b din propoziție.

Date de ieşire

În fişierul de ieşire manuscris.out, pe prima linie, afișați numărul de înțelesuri posibile diferite ale propoziției date, modulo 10⁹ + 7.

Restricții

• 2 ≤ N ≤ 200.000
• 2 ≤ K ≤ 1.000.000
• Pentru teste în valoare de 15 puncte N ≤ 7 și K = 2
• Pentru alte teste în valoare de 5 puncte N = 8 și K = 2
• Pentru alte teste în valoare de 5 puncte N = 9 și K = 2
• Pentru alte teste în valoare de 5 puncte N = 10 și K = 2

Exemplu

Explicaţie

În primul exemplu, există trei cazuri:

• ambele noduri au culoarea 1
• ambele noduri au culoarea 2
• un nod are culoarea 1, iar celălalt are culoarea 2

Cum se trimit solutii?