piese

Ion este un tânăr muzician și studiază chitara clasică. La un spectacol în aer liber, Ion a fost invitat să interpreteze câteva dintre piesele sale. Ion are în repertoriu $n$ piese, a căror durată este $t_1$, $t_2$, $\dots$, $t_n$ și ştie că timpul care-i va fi alocat nu poate depăşi $T$ unităţi de timp.

Pentru alegerea pieselor, Ion este interesat să ştie câte variante distincte are de a interpreta cel puţin o piesă în spectacol, astfel încât durata totală a pieselor interpretate să nu depăşească $T$. Două variante sunt distincte dacă există cel puţin o melodie care se găseşte într-o variantă şi nu se găseşte în cealaltă variantă.

Cerinţă

Cunoscând $n$, $T$ și duratele pieselor, determinaţi numărul de variante distincte pe care le are Ion de a interpreta piese astfel încât durata lor să nu depăşească $T$.

Date de intrare

Fişierul de intrare piese.in conține pe prima linie numerele $n$ şi $T$ având semnificaţia din enunţ. Pe linia a doua se găsesc $n$ numere naturale $t_1$, $t_2$, $\dots$, $t_n$, separate printr-un singur spaţiu, reprezentând duratele pieselor din repertoriul lui Ion.

Date de ieșire

Fişierul de ieșire piese.out va conţine pe o singură linie un număr natural ce reprezintă numărul de variante distincte pe care le are Ion de a interpreta piese din repertoriul său, astfel încât durata lor să nu depăşească $T$.

Restricții și precizări

• $2 \leq n \leq 30$
• $1 \leq x_1, x_2, \dots, x_n, T \leq 1 \ 000 \ 000 \ 000$
• Ordinea de prezentare a pieselor în spectacol nu este relevantă.

Exemplul 1

piese.in

3 2
4 3 5

piese.out

0

Explicație

Nu există nicio variantă. Toate piesele durează mai mult de $T$ unități de timp.

Exemplul 2

piese.in

4 6
2 4 5 1

piese.out

8

Explicație

Sunt 8 variante posibile: $2$, $4$, $5$, $1$, $2$ + $4$, $2$ + $1$, $4$ + $1$, $5$ + $1$