10092번 - Decreasing Sequences of Points 다국어

문제

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.

입력

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.

제한

• n ≤ 10000;
• 0 ≤ a_i ≤ 10000 for i = 1, 2, ..., n;
• a_i ≠ a_i+1 for i = 1, 2, ..., n - 1;

힌트