Problem iepuri


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şiere 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 şi precizări

  • 1<= N, K <= 100
  • Numărul ce trebuie scris în fişierul de ieşire va fi afişat modulo 30011.

Exemplu

iepuri.in

9 4
7 2
7 3
7 4
3 5
3 6
5 8
5 9
6 1

iepuri.out

9

General info

ID: 45

Upload: liviu

Input: iepuri.in/iepuri.out

Memory limit: 16MB/8MB

Time limit: 0.02s

Author: Iolanda Popa

Source: OJI 2008 XI-XII: Problema 1

Submissions

Special Submissions