Даны номиналы монет и сумма S. Найдите количество способов разменять сумму S данными монетами. Каждую монету можно использовать неограниченное число раз.
Важно: наборы, отличающиеся только порядком монет, считаются одинаковыми! Например, 1+2 и 2+1 — это один способ.
Формат входных данных
Первая строка: номиналы монет через пробел (от 1 до 5 монет)
Вторая строка: сумма S (1 ≤ S ≤ 20)
Формат выходных данных
Одно число — количество способов размена.
Примечание
В тестовом примере способы разменять 4:
Всего 3 способа.
ПОДСКАЗКА:
Чтобы избежать повторений (1+2 и 2+1), перебирай монеты в определённом порядке: каждая следующая монета должна быть не меньше предыдущей.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1 2
4
|
3
|