Кич, Поч и сарай
Родители Кича и Поча отправили их в деревню к бабушке. Ребятам было очень скучно и они решили поиграть в сарае, но в какой-то момент они случайно подожгли этот сарай. Теперь им нужно построить сарай заново.
Так они попали в магазин досок. В магазине имеется типов досок со стоимостью . У ребят имеется денег. Перед тем как купить нужные им доски, они решили ответить на вопрос: сколько различных способов существует, чтобы купить доски с бюджетом не более .
Стоит учесть, что доску одного типа можно покупать неограниченное количество раз.
Так как ответ может быть слишком большим, необходимо вывести его по модулю .
Вхідні дані
В первой строке заданы два целых числа и — количество досок и количество денег у ребят соответственно.
Во второй строке вводится чисел — стоимость доски -го типа.
Вихідні дані
Вывод содержит единственное целое число — ответ на задачу.
Приклади
Обратите внимание, что порядок досок важен. Например, вариант купить доски сначала 1-го типа, а затем 2-го типа и вариант купить доски сначала 2-го типа, а затем 1-го типа считаются различными.