Un gospodar are N iepuri (pe care i-a numerotat de la 1 la N) şi foarte mulţi morcovi. Ce e mai deosebit în această gospodărie este că iepurii sunt organizaţi ierarhic, în funcţie de vârstă, autoritate şi nevoile nutriţionale. Astfel, fiecare iepure are exact un şef direct (exceptându-l pe Rilă Iepurilă, care este şeful cel mare, şeful tuturor iepurilor). Orice iepure poate avea 0, 1 sau mai mulţi subordonaţi direcţi. Orice iepure-şef va mânca cel puţin un morcov mai puţin decât fiecare dintre subordonaţii săi direcţi.
Gospodarul nu se poate hotărî câţi morcovi să dea fiecărui iepure şi ar vrea să ştie în câte moduri poate împărţi morcovi la iepuri ştiind că fiecare iepure poate să mănânce minim un morcov şi maxim K morcovi.
Cerinţă
Scrieţi un program care calculează numărul de posibilităţi modulo 30011 de a împărţi morcovi la cei N iepuri ştiind că orice iepure poate mânca între 1 şi K morcovi şi trebuie să mănânce cu cel puţin un morcov mai puţin decât fiecare dintre iepurii care îi sunt subordonaţi direcţi.
Date de intrare
Fişierul de intrare iepuri.in conţine:
- pe prima linie două numere naturale N şi K, separate printr-un spaţiu, reprezentând numărul de iepuri, respectiv numărul maxim de morcovi ce pot fi mâncaţi de un iepure.
- pe fiecare din următoarele N-1 linii se află câte două numere naturale distincte a şi b, cuprinse între 1 şi N, separate printr-un spaţiu, cu semnificaţia că iepurele a este şeful direct al iepurelui b.
Date de ieşire
Fişierul de ieşire iepuri.out va conţine numărul de moduri de a împărţi morcovii conform condiţiilor specificate în enunţ, modulo 30011.
Restricţii
1<= N, K <= 100
Numărul ce trebuie scris în fişierul de ieşire va fi afişat modulo 30011.