В старой чайной лавке готовят подарочный набор ровно на S граммов. Для этого есть n видов чая. Для каждого вида известен вес одной стандартной порции. Порции одного и того же вида можно брать сколько угодно раз.

Нужно определить, сколькими различными способами можно собрать набор ровно на S граммов.

Два способа считаются различными, если для какого-то вида чая количество взятых порций отличается. Порядок выбора порций не важен.

Входные данные

В первой строке записаны два целых числа S и n — требуемый вес набора и количество видов чая.

Во второй строке записаны n различных целых чисел a1, a2, ..., an, где ai — вес одной порции чая i-го вида.

Выходные данные

Выведите одно целое число — количество различных способов собрать набор ровно на S граммов.

Гарантируется, что ответ помещается в знаковый 64-битный целый тип.

Ограничения

• 0 <= S <= 5000
• 1 <= n <= 300
• 1 <= ai <= 5000
• Все значения ai различны

Пример 1

Входные данные

5 3
1 2 5

Выходные данные

4

Пример 2

Входные данные

3 2
2 5

Выходные данные

0

Пример 3

Входные данные

10 4
2 3 5 6

Выходные данные

5

Пояснение к первому примеру

Набор на 5 граммов можно собрать четырьмя способами:

• 1 + 1 + 1 + 1 + 1
• 1 + 1 + 1 + 2
• 1 + 2 + 2
• 5

Комбинации 1 + 2 + 2 и 2 + 1 + 2 считаются одним и тем же способом, так как важны только количества порций каждого вида, а не порядок выбора.