Сладкие забавы

Маленькие сладкоежки Сережа и Юля очень любят конфеты. Родители детей это знают, и потому у них не возникает вопросов о том, что ребятишкам дарить в день рождения.

А тут подвернулся особый случай – обоим ребятишкам исполняется по 10 лет, и потому родители подсказали приглашенным гостям, чему дети больше всего обрадуются на их общем юбилее.

Гостей в день рождения собралось достаточно много – N человек. Гость, пришедший i-м по счету, подарил детям коробку, содержащую A_i конфет. Коробки конфет были как совсем маленькие, так и невероятно большие. Коробки были с прозрачными крышками и было видно, сколько там конфет.

Чтобы все было честно, дети решили поделить коробки так, чтобы каждому досталось не менее K конфет. Однако дети обнаружили, что сделать это можно многими способами. Ваша задача – определить количество различных способов честного дележа конфет, учитывая, что коробки не вскрываются и конфеты поштучно не делятся, и каждая коробка должна достаться только одному из ребятишек. Два варианта деления конфет считаются различными, если существует коробка конфет, которая в данных вариантах принадлежит разным детям.

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

Первая строка входного файла INPUT.TXT содержит два натуральных числа N и K соответственно (1 ≤ N ≤ 50; 1 ≤ K ≤ 10000). Числа в строке разделены одиночным пробелом.

Вторая строка содержит N натуральных чисел A_i (1 ≤ i ≤ N, 1 ≤ A_i ≤ 10⁹), разделенных одиночными пробелами, где число A_i – это количество конфет в коробке, подаренной гостем, пришедшим i-м по счету.

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

Единственная строка выходного файла OUTPUT.TXT должна содержать одно целое число — количество способов честно поделить конфеты между детьми.

Примеры

Пояснение

Для первого примера варианты разбиения (номера коробок, доставшихся, например, Сереже): 3, 1 2, 1 3, 1 4, 2 3, 2 4, 3 4, 1 2 4.

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]