Autostrăzi

Autostrazi

== include(page="template/taskheader" task_id="autostrazi") ==

Într-o ţară care-şi caută drumul spre bunăstare şi civilizaţie, există $N$ oraşe, numerotate de la $1$ la $N$, legateîntre ele prin $N – 1$ şosele bidirecţionale. Între oricare două oraşe există cel mult o singură şosea. Fiecare şosea uneşte două oraşe distincte. Se poate călători între oricare două oraşe, circulând numai pe şosele. Din păcate, nu există autostrăzi. Nu există nici bani pentru construirea autostrăzilor.  Din acest motiv, politica statului este de a concesiona şoselele celor $K$ „regi ai asfaltului”. Aceştia vor construi autostrăzi pe cheltuiala lor, având apoi dreptul de a impune taxe de trecere pe autostradă, exprimate în euro. Fiecare autostradă astfel construită va înlocui una dintre sosele.

Într-o ţară care-şi caută drumul spre bunăstare şi civilizaţie, există $N$ oraşe, numerotate de la $1$ la $N$, legate între ele prin $N – 1$ şosele bidirecţionale. Între oricare două oraşe există cel mult o singură şosea. Fiecare şosea uneşte două oraşe distincte. Se poate călători între oricare două oraşe, circulând numai pe şosele. Din păcate, nu există autostrăzi. Nu există nici bani pentru construirea autostrăzilor. Din acest motiv, politica statului este de a concesiona şoselele celor $K$ „regi ai asfaltului”. Aceştia vor construi autostrăzi pe cheltuiala lor, având apoi dreptul de a impune taxe de trecere pe autostradă, exprimate în euro. Fiecare autostradă astfel construită va înlocui una dintre şosele.

h2. Cerintă

h2. Cerinţă

Scrieţi un program care calculează numărul de moduri modulo $30011$ în care se pot concesiona şoselele, astfel încât pentru niciun vehicul care se deplasează între oricare două orase ale ţării mergând pe şosele şi autostrăzi să nu se depăşească un total al taxelor mai mare decât $S$ euro.

4901