Let A₁(x₁,y₁), A₂(x₂,y₂), ..., 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,4), A₂(1,3), A₃(2,2), A₄(2,1), A₅(4,0), A₆(7,0), is decreasing.

Write program points, which calculates the number of decreasing sequences of points for which x₁+y₁=a₁, x₂+y₂=a₂, ..., 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₁, a₂, ..., 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