Размен без порядка


Отправить решение Решать в редакторе

Сложность: 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

Комментарии

Еще нет ни одного комментария.