Получить количество различных множеств продуктов, соответствующих вышесказанной истории Вити по модулю 109+7.

Сегодня вечером Витя, самый обычный житель, решил посетить магазин и купить продукты для дома. В магазине есть всего n продуктов. Цена i-го из них равна ai тенге.

У Вити с собой в кармане есть ровно m тенге. Он уже выбрал k≥2 продуктов, но оказалось что их общая стоимость превышает его бюджет. К счастью, у него получилось убрать ровно один из них и его денег хватило на покупку всех остальных k−1 продуктов.

На следующий день Витя рассказал об этом своему другу Пете. Петя не поверил ему на слово, поэтому решил это проверить. Сколько вообще различных множеств продуктов Витя мог выбрать из магазина так, чтобы вышесказанные слова Вити являлись правдой? Поскольку ответ может быть очень большим, надо найти остаток от его деления на 109+7. Два множества считаются различными, если существует продукт x который присутствует в одном множестве, но отсутствует в другом.

Входные данные
В первой строке входного файла даны два положительных целых числа n и m (2≤n≤100, 1≤m≤10000).

Во второй строке даны n целых чисел a1, ..., an — цены всех продуктов (1≤ai≤10000).

Выходные данные
Выведите единственное целое число — количество различных множеств продуктов соответствующих вышесказанной истории Вити по модулю 109+7.

0