Ви працюєте на касі на веселому ярмарку, і у Вас є різні номінали монет. Монети кожного номіналу доступні у нескінченній кількості. Вартість кожного номіналу відома. Визначте кількість способів, якими можна сплатити задану суму, використовуючи монети наявних номіналів.
Наприклад, якщо у Вас є 4 номінали монет вартістю 8,3,1,2, то суму 3 можна видати такими способами: {1,1,1},{1,2} та {3}.
Перший рядок містить два цілих числа: суму n (1≤n≤250) і кількість номіналів монет m (1≤m≤50). Другий рядок містить m цілих чисел ci (1≤ci≤50), що описують вартість номіналів монет. Усі значення ci різні.
Виведіть кількість способів, якими можна сплатити суму n.