E. Devu и цветы
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Devu хочет декорировать свой сад. Он приобрел n коробок с цветами, i-я коробка содержит fi цветов. Все цветы в одной коробке одного цвета (поэтому они неразличимы). Также среди коробок нет двух с одинаковыми цветами.

Devu хочет выбрать ровно s цветов из коробок, чтобы украсить свой сад. Сколькими способами он может это сделать? Так как это число может быть очень большим, найдите его по модулю 1000000007 (109 + 7).

Devu считает, что два способа различные, если в этих способах хотя бы из одной коробки выбрано разное количество цветов.

Входные данные

Первая строка содержит два разделенных пробелом целых числа n и s (1 ≤ n ≤ 20; 0 ≤ s ≤ 1014).

Вторая строка содержит n целых чисел, записанных через пробел, f1, f2, ... fn (0 ≤ fi ≤ 1012).

Выходные данные

Выведите целое число — количество способов выбрать s цветов по модулю 1000000007 (109 + 7).

Примеры
Входные данные
2 3
1 3
Выходные данные
2
Входные данные
2 4
2 2
Выходные данные
1
Входные данные
3 5
1 3 2
Выходные данные
3
Примечание

Пример 1. Есть два способа выбрать 3 цветка: {1, 2} и {0, 3}.

Пример 2. Есть только один способ выбора 4 цветков: {2, 2}.

Пример 3. Есть три способа выбора 5 цветков: {1, 2, 2}; {0, 3, 2}; {1, 3, 1}.