Размен без порядка
Отправить решение
Решать в редакторе
Сложность:
42%
Очки:
100 (частичный балл)
Ограничение по времени:
2.0s
Ограничение по памяти:
256M
Автор:
Типы задач
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch
Размен без порядка
Есть монеты k различных номиналов, каждого номинала сколько угодно. Сколькими способами можно набрать ровно S сомов, если способы, отличающиеся только порядком монет, считаются одинаковыми? Ответ по модулю 10⁹+7.
Формат ввода
В первой строке k и S (1 ≤ k ≤ 50, 0 ≤ S ≤ 10⁵). Во второй — k различных номиналов (1 ≤ cᵢ ≤ 10⁵).
Формат вывода
Число способов по модулю 10⁹+7.
Пример 1
Вход:
3 5
1 2 5
Выход:
4
Пример 2
Вход:
1 3
2
Выход:
0
Комментарии