Жетоны для аркады

В игровой аркаде можно пополнять счёт жетонами разных номиналов. Автомат выдаёт жетоны неограниченно: каждого номинала можно взять сколько угодно раз.

Ты хочешь собрать ровно сумму S. Два способа считаются одинаковыми, если в них взято одинаковое количество жетонов каждого номинала (то есть порядок жетонов не важен).

Найди, сколько существует способов собрать сумму S. Ответ выведи по модулю 1000000007.

Важно: количество способов может быть очень большим (на олимпиадах это превышает 32-битный тип; в Python это не проблема, но модуль обязателен).

Формат ввода

Первая строка: два целых числа n и S — количество номиналов и нужная сумма. Вторая строка: n целых чисел c1, c2, ..., cn — номиналы жетонов.

Формат вывода

Одно целое число — количество способов собрать сумму S из данных номиналов (каждый можно использовать неограниченно), по модулю 1000000007.

Ограничения

• 1 ≤ n ≤ 50
• 0 ≤ S ≤ 5000
• 1 ≤ ci ≤ 5000

Пример

Ввод:

3 7
2 3 5

Вывод:

2

Пояснение: можно собрать 7 как 2+5 и как 2+2+3.

Ключевое наблюдение: порядок жетонов не важен, значит мы считаем сочетания, а не перестановки. Поэтому нельзя «перебирать следующую монету» как отдельный шаг в любой момент — нужно фиксировать порядок обработки номиналов.

Подходит приём «динамика по сумме»: пусть dp[x] — число способов набрать сумму x, используя только первые обработанные номиналы. Тогда, когда добавляем новый номинал c, мы можем либо не брать его, либо взять ещё один c поверх уже набранной суммы x-c.

Главное, почему работает: если внешний цикл идёт по номиналам, каждый набор количеств монет будет посчитан ровно один раз (в момент, когда обрабатывается его «самый большой по порядку» номинал).

План:

• Задай модуль MOD = 1000000007.
• Создай массив dp длины S+1, заполни нулями.
• База: dp[0] = 1 (сумму 0 можно набрать «ничем» — один способ).
• Для каждого номинала c:
• Для x от c до S (вперёд!): обнови dp[x] по правилу dp[x] = (dp[x] + dp[x-c]) % MOD.
• Ответ: dp[S].

Сложность: O(n * S) по времени и O(S) по памяти, что подходит при n ≤ 50, S ≤ 5000.

Частая грабля: перепутать порядок циклов или идти по x назад. Тогда будут считаться разные порядки жетонов (перестановки) или сломается «неограниченность» использования монеты.