Decreasing Sequences of Points

Time limit1sMemory limit256 MB

Summary

Count sequences of lattice points on the diagonals x+y=a_i with nondecreasing x and nonincreasing y.

Level: Medium6 of 10
Topics: Dynamic programming, Prefix sum
Solved: No attempts yet

Problem

Consider a sequence of distinct points $A_1(x_1, y_1), A_2(x_2, y_2), \ldots, A_n(x_n, y_n)$ with nonnegative integer coordinates. The sequence is decreasing if $x_i \le x_{i+1}$ and $y_i \ge y_{i+1}$ for every $i$ .

Count how many decreasing sequences satisfy $x_1 + y_1 = a_1, x_2 + y_2 = a_2, \ldots, x_n + y_n = a_n$ .

Input

The first line contains a positive integer $n$ . The second line contains $n$ nonnegative integers $a_1, a_2, \ldots, a_n$ .

Output

Print the number of valid sequences modulo $123456789$ .

Constraints

$n \le 10000$
$0 \le a_i \le 10000$
$a_i \ne a_{i+1}$

Examples6

Example 1
Input
```
3
4 5 3
```
Expected output
```
10
```
Example 2
Input
```
1
0
```
Expected output
```
1
```
Example 3
Input
```
1
5
```
Expected output
```
6
```
Example 4
Input
```
2
1 2
```
Expected output
```
3
```
Example 5
Input
```
2
3 7
```
Expected output
```
10
```
Example 6
Input
```
4
1 2 3 4
```
Expected output
```
5
```