Задача K. Дайсы ≡

Условие

Тимофей увлекся настольными ролевыми играми. В его речи всё чаще встречаются непонятные окружающим термины "билд", "данж", "отыгрыш", "каст с хитов" и тому подобные. Все карманные деньги Тимофей тратит на фигурки персонажей, карты подземелий и, конечно, наборы игральных костей (дайсы) без которых не обходится ни одна партия.

Дайс представляет собой многогранник, на сторонах которого записаны числа. В коллекции Тимофея собраны разнообразнейшие кубики, которые позволяют генерировать выпадение любых натуральных чисел. Для удобства Тимофей описывает каждый дайс максимальным числом, которое записано на одной из его граней. Например, дайс5 позволяет выбросить любое целое число от 1 до 5 включительно, а дайс100 - от 1 до 100.

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

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

В первой строке через пробел записаны два натуральных числа n и s - количество дайсов и сумма очков. Во второй строке через пробел записаны n натуральных чисел d_i - описание i-го дайса.

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

Выведете одно неотрицательное целое число - количество способов. Предупреждение - ответ может быть очень большой.

Ограничения

1 ≤ n ≤ 100

1 ≤ s ≤ 10⁹

2 ≤ d_i ≤ 100

Система оценки и описание подзадач

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.

Подзадача 1: n = 1, баллы: 10.

Подзадача 2: n = 2, баллы: 20.

Подзадача 3: n ≤ 12, d_i = 2, баллы: 20.

Подзадача 4: нет дополнительных ограничений, баллы: 50.

Пояснения к примерам

Комментарий к первому примеру: существует единственный способ выбросить 1 с помощью одного стандартного шестигранного игрального кубика.

Комментарий ко второму примеру: у Тимофея два дайса: первый позволяет выбрасывать числа от 1 до 2, второй - от 1 до 6. Число 4 можно набрать двумя способами: выбросить 1 на первом дайсе и 3 на втором или выбросить 2 на обоих дайсах.

Комментарий к третьему примеру: сумму 4 с помощью пяти дайсов получить невозможно.

Примеры тестов

1 1
6

1

2 4
2 6

2

5 4
2 3 2 7 100

0