Odată cu vacanţa de Paşte, Alex s-a hotărât să plece cu maşina la mare. Harta României este modelată ca un arbore (graf conex aciclic neorientat) ce are N noduri, reprezentând oraşele ţării. Este binecunoscut faptul că Alex este vitezoman, de aceea el vrea să se ferească de eventualele radare, care sunt plasate pe muchiile arborelui (pe o muchie se poate afla maxim un radar). Dacă pe o muchie există un radar, atunci Alex nu va risca şi nu va merge pe acea muchie.
Fiecare oraş are un timp de vizitare dat, iar cu toţii ştim că Alex este foarte ocupat, aşadar el nu vrea sa piardă prea mult timp vizitând. Alex pleacă din Gheorgheni (nodul 1, considerat rădăcină) şi doreşte să ştie în câte moduri ar putea fi plasate radarele pe hartă astfel încât timpul total de vizitare al oraşelor accesibile din nodul 1 să fie egal cu P, ştiind că Alex nu va merge pe nicio muchie ce conţine un radar.
Problema aceasta este destul de simplă pentru Alex, aşa că s-a gândit să v-o dea vouă.
Cerinţă
Scrieţi un program care să răspundă problemei lui Alex, adică să determine în câte moduri pot fi plasate radare pe muchii astfel încât timpul total de vizitare al oraşelor accesibile din nodul 1 să fie egal cu P.
Date de intrare
Fişierul radare.in conţine pe prima linie N şi P, cu semnificaţia din enunţ. Următoarele N-1 linii vor conţine fiecare câte două numere întregi x y, însemnând că există o muchie între oraşele x şi y.
Pe ultima linie se vor afla N numere naturale cuprinse între 1 şi P inclusiv, al i-lea dintre acestea reprezentând timpul de vizitare al oraşului i.
Date de ieşire
Fişierul radare.out va conţine un singur număr reprezentând răspunsul problemei lui Alex modulo 31333.
Restricţii
• 1 ≤ N ≤ 3 000
• 1 ≤ P ≤ 3 500
• 1 ≤ x, y ≤ N
• 1 ≤ timpul de vizitare al unui oraş ≤ P
• dacă un radar este plasat pe o muchie, Alex NU va merge pe acea muchie
• două configuraţii de radare diferă între ele dacă există cel puţin o muchie (a, b) care într-una dintre configuraţii să conţină un radar, iar în cealaltă nu.
Exemple
radare.in
radare.out
Explicaţii
6 3
1 2
1 3
2 4
4 5
4 6
1 1 1 1 1 1
5
Cele 5 moduri posibile sunt:
1. există radar pe muchia (2,4)
2. sunt radare pe muchiile (2,4), (4,5)
3. sunt radare pe muchiile (2,4), (4,6)
4. sunt radare pe muchiile (2, 4), (4,5), (4,6)
5. sunt radare pe muchiile (1,3), (4,5), (4,6)
