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