Codeforces Round 258 (Div. 2) |
---|
Закончено |
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}.
Название |
---|