Devu хочет декорировать свой сад. Он приобрел n коробок с цветами, i-я коробка содержит fi цветов. Все цветы в одной коробке одного цвета (поэтому они неразличимы). Также среди коробок нет двух с одинаковыми цветами.
Devu хочет выбрать ровно s цветов из коробок, чтобы украсить свой сад. Сколькими способами он может это сделать? Так как это число может быть очень большим, найдите его по модулю 1000000007 (109 + 7).
Devu считает, что два способа различные, если в этих способах хотя бы из одной коробки выбрано разное количество цветов.
Выходные данные
Выведите целое число — количество способов выбрать s цветов по модулю 1000000007 (109 + 7).
Примечание
Пример 1. Есть два способа выбрать 3 цветка: {1, 2} и {0, 3}.
Пример 2. Есть только один способ выбора 4 цветков: {2, 2}.
Пример 3. Есть три способа выбора 5 цветков: {1, 2, 2}; {0, 3, 2}; {1, 3, 1}.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 3
1 3
|
2
|
|
2
|
2 4
2 2
|
1
|
|
3
|
3 5
1 3 2
|
3
|