Числовая пирамида
"Кому нужно ядерное оружие, если у Вас есть такая мощь как Интернет?"
Лия Вакефиелд
На рисунке изображена числовая пирамида. Путь всегда начинается на вершине пирамиды и заканчивается внизу. Разрешено перемещаться только на соседние ячейки пирамиды, расположенные ниже. Стоимость пути равна сумме чисел в ячейках на пройденном пути (включая первую и последнюю).
Зная значение всех чисел в ячейках пирамиды и некоторое число S, подсчитайте количество путей, стоимость которых равна S.
Входные данные
Входные данные состоят из нескольких тестовых случаев. Каждый тестовый случай начинается строкой, в которой заданы два целых числа N и S (2 ≤ N ≤ 50, 0 ≤ S < 500), соответственно высота пирамиды и заданная стоимость пути. Далее следует N строк, описывающих саму числовую пирамиду. В каждой из этих строк размещены разделённые пробелами числа от 0 до 9. Первая строка содержит одно число, вторая - 2, ..., предпоследняя - N-1, последняя - N чисел.
Входные данные заканчиваются строкой, содержащей N = S = 0. Эта строка не обрабатывается. В одном тесте содержится не более 30 тестовых случаев.
Выходные данные
Для каждого случая выведите количество указанных путей.