Restaurant Ratings

A travel web site has a new restaurant rating system. Each restaurant is rated by $n$ critics ($1 \le n \le 15$), and every critic gives it a nonnegative integer score. A higher score is a better score. Some critics carry more weight than others.

The restaurants of a city are ranked as follows. First, add up the scores given by all critics. A restaurant with a larger total is always better than one with a smaller total. When two totals are equal, compare the scores given by critic 1, and the higher score is better. If those scores are equal as well, compare critic 2, then critic 3, and so on down the order.

An owner received the score sheet of his restaurant and wants to know where it stands in the city. He does not know the scores of the other restaurants, so he estimates the position by counting how many distinct score sheets are no better than his own. A score sheet is a sequence of $n$ nonnegative integers listed in critic order, and his own sheet is counted too. Write a program that answers his question.

The input holds several test cases, one per line. On each line the first integer is $n$, followed by the $n$ scores in critic order. The total of the scores of a restaurant is at most 30. A line containing $n = 0$ ends the input.

For each test case, print on its own line the number of distinct score sheets that are no better than the given one. The answer fits in a 64-bit signed integer.