Вы работаете на кассе на веселой ярмарке, и у Вас имеются различные номиналы монет. Монеты каждого номинала доступны в бесконечном количестве. Стоимость каждого номинала известна. Определите количество способов, которыми можно оплатить заданную сумму, используя монеты имеющихся номиналов.
Например, если у Вас имеются номинала монет стоимостью , то сумму можно выдать следующими способами: и .
Первая строка содержит два целых числа: сумму и количество номиналов монет . Вторая строка содержит целых чисел , описывающих стоимости номиналов монет. Все значения различны.
Выведите количество способов, которыми можно оплатить сумму .