Ви працюєте на кас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