Ви працюєте на касi на розважальному ярмарку i у вас є рiзнi номiнали монет, якi доступнi вам у нескiнченних кiлькостях. Значення кожної монети дається. Необхiдно визначити кiлькiсть способiв набору певної суми за допомогою заданих номiналiв монет?

Наприклад, якщо у вас є 4 типи монет, а номiнали задано вiдповiдно 8,3,2,1, ви можете набрати суму 3 трьома способами: {1,1,1}, {1,2} i {3}.

Формат вхiдних даних

Перший рядок мiстить два цiлих цiлих числа \(n\) \((1 \le n \le 250)\) та \(m\) \((1 \le m \le 50)\), де:

\(n\) - сума, яку треба набрати;

\(m\) - кiлькiсть номiналiв монет.

Другий рядок мiстить цiлi числа, що описують вiдповiднi значення кожного номiналу монет: \(c_0, c_1 ,...,c_{m−1}\) \((1 \le c_i \le 50)\)

Формат вихiдних даних

Вивести одне число - кiлькiсть способiв набору суми \(n\) даними номiналами монет.

Приклад вхідних даних

4 3
1 2 3

Приклад вихідних даних

4