Числова піраміда#1471
На малюнку зображено числову піраміду. Шлях завжди починається у верхній частині піраміди та закінчується на її основі. Кожна клітинка шляху (крім першої) повинна знаходитися прямо під і зліва або справа від клітинки шляху у попередньому рядку. Значення шляху — це сума чисел усіх клітинок, які входять у цей шлях.
Вам задані значення чисел у піраміді, а також ціле число . Потрібно обчислити кількість різних шляхів зі значенням .
Вхід містить кілька тестових випадків. Кожен тестовий випадок починається з рядка з двома цілими числами і (2 \leq N \leq 50, 0 \leq S < 500) — висота піраміди та бажана сума відповідно. Далі йде рядків з описом піраміди. Кожен із цих рядків містить список чисел від до , розділених пробілами. У першому з них буде одне число, у другому — два, і так далі до .
Вхід закінчується рядком N = S = 0. Цей тестовий випадок обробляти не потрібно. Загалом у вхідних даних менше тестових випадків.
Для кожного тестового випадку виведіть кількість різних шляхів.
Приклад 1