Consider a nondecreasing sequence of integers ( for ). The sequence defined by , for , is called the mean sequence of sequence . For example, the mean sequence of sequence is the sequence . Note that elements of the mean sequence can be fractions. However, this task deals with mean sequences whose elements are integers only.

Given a nondecreasing sequence of integers , compute the number of nondecreasing sequences of integers that have the given sequence as mean sequence.

#### Task

Write a program that:

- reads from the standard input a nondecreasing sequence of integers,
- calculates the number of nondecreasing sequences, for which the given sequence is mean sequence,
- writes the answer to the standard output.

#### Input

The first line of the standard input contains one integer . The remaining lines contain the sequence . Line contains a single integer . You can assume that in of the test cases and .

#### Output

Your program should write to the standard output exactly one integer — the number of nondecreasing integer sequences, that have the input sequence as the mean sequence.

#### Sample Input

```
3
2
5
9
```

#### Sample Output

`4`

#### Explanation for Sample Output

Indeed, there are four nondecreasing integer sequences for which is the mean sequence. These sequences are:

- ,
- ,
- ,
- .

## Comments