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

Poveste şi cerinţă...

Î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.
 
h2. Cerinta
 
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.
 

h2. Date de intrare

Fişierul de intrare $autostrazi.in$ ...

Pe prima linie a fişierului de intrare autostrazi.in se află trei numere întregi N, S si K separate printr-
un singur spaţiu, cu semnificaţia din enunţ. Pe linia următoare se află K numere naturale, R1, R2, .. Rk, nu
neapărat distincte, separate printr-un singur spaţiu, reprezentând taxele percepute de regii asfaltului. Pe
următoarele N – 1 linii se găsesc câte două numere naturale distincte x şi y separate printr-un singur spaţiu
reprezentând o şosea care leagă oraşul x de oraşul y.
 

h2. Date de ieşire

În fişierul de ieşire $autostrazi.out$ ...

În fişierul de ieşire autostrazi.out se află un singur număr natural M, reprezentând numărul de
posibilităţi modulo 30011 în care poate fi construită reţeaua de autostrăzi, astfel încat suma taxelor plătite
într-o călătorie între oricare două oraşe să nu depăşească S euro.
 

h2. Restricţii

* $... ≤ ... ≤ ...$

Restricţii şi precizări
• 1 ≤ x, y ≤ N ≤ 100
• 1 ≤ K ≤ 20
• 1 ≤ S ≤ 100
• 1 ≤ R1, R2, .. Rk ≤ 100
• Regele i al asfaltului impune aceeaşi taxă Ri pentru fiecare autostradă constuită de el şi poate construi
   zero, una sau maxim N – 1 autostrăzi.
• O şosea se concesionează în întregime unui singur constructor sau poate să nu fie concesionată deloc. În
   acest caz nu există taxă de trecere.
• Este admis cazul în care nu se concesionează nicio şosea.
 

h2. Exemplu
table(example). |_. autostrazi.in |_. autostrazi.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|4 2 2
2 1
1 2
2 3
4 2
 
| 11

|
h3. Explicaţie

...

Taxele: 2 si 1. Şoselele : 2 1, 2 3, 2 4
Variantele de taxare:
(0 0 0), (1 0 0), (0 1 0), (0 0 1), (1 1 0),
(0 1 1), (1 0 1), (1 1 1), (2 0 0), (0 2 0),
(0 0 2)
 

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