Тема: Возникла проблема в одной задаче, никак подход не могу найти:
Возникла проблема в одной задаче, никак подход не могу найти:
Вася решил организовать турнир. Он получил n коробок с призами от спонсора. Каждая коробка содержит разные призы, но в каждой коробке призы одинаковые. Из накладной известно, что в i-й коробке содержится mi одинаковых призов. Васька решил наградить команду, которая победила. Команда может получить не меньше a призов, и не больше чем b призов. Теперь перед Василием встал вопрос: сколько дать призов команде-победителю и каких? Задача - подсчитать сколькими способами он может распределить призы.
Программа читает в одном рядке три целых числа: n, a и b, разделённые одним пропуском(1≤n≤10, 0≤a≤b≤10 000 000). Каждое из следующих n целых чисел такие, что i+3 число - это mi – количество конфет в i упаковке. (0≤mi≤1000000). Программа выводит на устройство стандартного вывода k mod 10^9+7.
Пример:
Ввод - 2 1 3 3 5
Вывод - 9
(Способы распределения: (1,0),(2,0),(3,0),(0,1),(0,2),(0,3),(1,1),(1,2),(2,1))
Я пробовал сначала находить для каждого отдельного количества упаковок количество всех возможных комбинаций и отсекать ненужные, но быстро понял, что это слишком затратно, особенно для больших чисел. Также нашёл одну формулу (прикреплена), но она подразумевает деление, что не подходит из-за того, что мне нужно выдать остаток от деления на 10^9+7, а также искать факториалы чисел до 10^7 тоже не очень удобно.
Возможно стоит с помощью какого-нибудь алгоритма перебрать все возможные варианты для каждого количества подарков, найти их остаток от деления на 10^9+7, и потом суммировать и выводить, но какого алгоритма?
