# Points

Let A_{1}(x_{1},y_{1}), A_{2}(x_{2},y_{2}), ..., A_{n}(x_{n},y_{n}) be a sequence of n different points in the plane with nonnegative integer coordinates. We call this sequence decreasing if for any two
points A_{i}(x_{i},y_{i}) and A_{i+1}(x_{i+1},y_{i+1}) it is true that x_{i} <= x_{i+1} and y_{i} >= y_{i+1}. For example, the
sequence of points A_{1}(1,4), A_{2}(1,3), A_{3}(2,2), A_{4}(2,1), A_{5}(4,0), A_{6}(7,0), is decreasing.

Write program points, which calculates the number of decreasing sequences of points for which x_{1}+y_{1}=a_{1}, x_{2}+y_{2}=a_{2}, ..., x_{n}+y_{n}=a_{n}.

### Input

The positive integer n (1<=n<=10000) is given on the first line of the standard input. There are n nonnegative integers on the second line: a_{1}, a_{2}, ..., a_{n} (0<=a_{i}<=10000 and a_{i}<>a_{i+1}).

### Output

On a line of the standard output the program has to write by modulo 123456789 the number of the above described sequences.

### Constraints

Time limit: 1 second

Memory limit: 64 megabytes

### Examples

input 3 4 5 3 | output 10 |