radare

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

• 1 ≤ N ≤ 3 000
• 1 ≤ P ≤ 3 500
• 1 ≤ x, y ≤ N
• 1 ≤ timpul de vizitare al unui oras ≤ 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 din configuraţii să conţină un radar, iar în cealaltă nu.
• pentru 30% din teste N ≤ 15
• pentru 50% din teste, timpii de vizitare pentru fiecare oraș vor fi 1
• pentru 60% teste, N ≤ 300

Exemplu

radare.in

6 3
1 2
1 3
2 4
4 5
4 6
1 1 1 1 1 1

radare.out

5

Explicaţie

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)