Задача №112623. Размен монет-2

Найдите количество различных способов разменять N рублей, если имеются монеты K типов достоинством V i рублей ( i = 1, ..., K ). Считайте, что есть неограниченное количество монет каждого типа.

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

Первая строка содержит одно натуральное число N – сумму, которую нужно разменять ( 1 ≤ N ≤ 10000 ). Во второй строке записано количество типов монет K ( 1 ≤ K ≤ 100 ). В третьей строке записаны K различных натуральных чисел, которые обозначают достоинство каждого типа монет.

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

Программа должна вывести одно число: количество различных вариантов размена. Гарантируется, что искомое число не превышает 2 31 - 1 .

Примеры
Входные данные
100
4
1 2 5 10
Выходные данные
2156
Сдать: для сдачи задач необходимо войти в систему