BigTasty

Ce-i în gușă și-n căpușă.

Cerință

Origu a mers la McDonald's. FNCSA-ul e cu ochii pe el. El nu știe ce dorește să mănânce, așa că se uită pe meniu. Meniul conține $n$ burgeri diferiți. Origu este pretențios, așa că are anumite restricții. Pentru fiecare burger, dacă îl cumpără, trebuie să ia exact $p_i$ bucăți din acel tip de burger. De asemenea, Origu se consideră un "Sigma Culinar", adică el consideră că ordinea în care mănâncă burgerii este importantă (burgerii de același tip sunt nediferențiabili). Ținând cont de aceste restricții, Origu vrea să afle în câte moduri își poate lua masa de prânz astfel încât să mănânce exact $m$ burgeri.

Date de intrare

Pe prima linie sunt două numere, $n$ și $m$, reprezentând numărul de burgeri din meniu, respectiv numărul de burgeri pe care vrea să îi mănânce Origu la prânz.
Pe a doua linie este un vector $p$ de $n$ elemente, unde $p_i$ reprezintă numărul de burgeri de tipul $i$ pe care Origu îi poate mânca, pentru orice $1 \le i \le n$.

Date de ieșire

Pe prima linie se va afișa restul împărțirii rezultatului la $10^9 + 7$.

Restricții și precizări

• $1 \le n, m \le 5\ 000$
• $1 \le p_i \le 5\ 000$

Exemplul 1

stdin

2 4
1 3

stdout

4

Explicație

Acestea sunt modurile în care Origu poate mânca burgerii :

Exemplul 2

stdin

19 37
19 4 20 7 18 9 2 3 18 11 13 4 14 13 20 3 3 1 2

stdout

779606264

Exemplul 3

stdin

3 5
2 2 3

stdout

20