Number Pyramid
"Who needs nuclear weapons when you have the power of the internet?"
Leah Wakefield
In the figure you see a number pyramid. A path always starts at the top of the pyramid and ends at the bottom. Each cell in the path (except the first) should be directly below to the left or right of the cell in the path in the upper row. The value of a path is the sum of the values of all cells in the path.
Given the values of each number in the pyramid as well as an integer S, calculate the number of distinct paths with value S.
Input
The input contains several cases. Each case starts with a line containing two integers N and S (2 ≤ N ≤ 50, 0 ≤ S < 500), the height of the pyramid and the desired sum. Next follows N lines describing pyramid. Each line contains a space separated list of integers between 0 and 9 inclusive. The first of these lines will contain one integer, then 2, ..., N-1, N.
The input will terminate with N = S = 0. This case should not be processed. There will be less than 30 cases in the input.
Output
For each case, output the number of distinct paths.