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.</p>

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.

입력 형식

The positive integer n is given on the first line of the standard input. There are n nonnegative integers on the second line: a₁, a₂, ..., a_n.

출력 형식

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

예제 입력

3
4 5 3

예제 출력

10