Number Pyramid#1471
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 , calculate the number of distinct paths with value .
The input contains several cases. Each case starts with a line containing two integers and (2 \leq N \leq 50, 0 \leq S < 500), representing the height of the pyramid and the desired sum, respectively. Next follows lines describing the pyramid. Each line contains a space-separated list of integers between and inclusive. The first of these lines will contain one integer, then , ..., N-1, .
The input will terminate with N = S = 0. This case should not be processed. There will be less than cases in the input.
For each case, output the number of distinct paths.
Example 1