== include(page="template/taskheader" task_id="colorare3") ==
Poveste şi cerinţă...
În Oraşul Simplu au avut loc de curând alegeri pentru funcţia de primar. Cel care a fost ales a câştigat mai ales datorită proiectului său de restaurare a faţadelor tuturor clădirilor, iar acum trebuie să-l pună în practică. Oraşul Simplu constă din $N$ obiective între care există străzi, în aşa fel încât pentru oricare 2 astfel de obiective există un singur drum de a ajunge de la unul la celălalt mergând pe străzi. Planul primarului constă în colorarea tuturor caselor astfel încât casele de pe aceeaşi stradă să aibă aceeaşi culoare, iar pentru oricare 2 străzi care se întâlnesc în acelaşi obiectiv, culorile să fie diferite. Ştiind ca primarul are la dispoziţie $K$ culori, ar vrea să afle câte posibilităţi sunt de a-şi realiza planul de colorare.
h2. Date de intrare
Fişierul de intrare $colorare3.in$ ...
Fişierul de intrare $colorare3.in$ conţine pe prima linie numerele $N$ şi $K$. Urmează $N - 1$ linii, fiecare conţinând câte 2 numere $a$ şi $b$ semnificând faptul că există o stradă între obiectivele $a$ şi $b$.
h2. Date de ieşire
În fişierul de ieşire $colorare3.out$ ...
În fişierul de ieşire $colorare3.out$ se va scrie numărul de posibilităţi de colorare modulo $1 000 000 007$.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 100 000$
* $1 ≤ K ≤ 1 000 000 000$
* Obiectivele sunt numerotate de la $1$ la $N$.
h2. Exemplu
table(example). |_. colorare3.in |_. colorare3.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 5 3
1 2
1 3
1 4
3 5
| 12
|
h3. Explicaţie
...
Se observă că după ce alegem culorile pentru străzile $(1,2)$, $(1,3)$, $(1,4)$ (având $6$ posibilităţi), strada $(3,5)$ poate fi colorată în $2$ moduri: cu aceeaşi culoare ca $(1,2)$ sau $(1,4)$. Cu mai puţin de $3$ culori nu se poate realiza planul. Aşadar, $6 * 2 = 12$.
== include(page="template/taskfooter" task_id="colorare3") ==
