Подсчёт наборов выработки панелей

В журнале солнечной электростанции записана суточная выработка отдельных панелей в ватт-часах. Каждая строка журнала соответствует отдельной панели, поэтому панели с одинаковой выработкой всё равно считаются разными.

Для плановой проверки нужно определить, сколькими способами можно выбрать набор панелей с суммарной выработкой ровно target ватт-часов. Набор задаётся подмножеством строк с известными значениями выработки: порядок выбора панелей не важен.

Значение -1 означает пропуск измерения: такая строка не может входить в набор и полностью игнорируется. Пусть известные выработки равны a1, a2, ..., ak. Требуется посчитать количество множеств индексов S ⊆ {1, 2, ..., k}, для которых

Σ ai = target по всем i ∈ S.

Выведите целое число без округления. Правила выбора при равенстве нет: требуется только одно число — количество всех подходящих наборов. Пустой набор допустим по определению, однако при заданных ограничениях он не может дать сумму target, так как target > 0.

Формат ввода

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

Во второй строке даны n целых чисел yield_1, yield_2, ..., yield_n — значения выработки панелей. Значение -1 обозначает пропуск измерения.

Формат вывода

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

Ограничения

• 1 ≤ n ≤ 4000;
• 1 ≤ target ≤ 2000;
• каждое yield_i равно -1 или является целым числом от 1 до 500;
• длина второй строки не превышает 20000 символов;
• пропуски измерений возможны в любом количестве, включая все n строк.