감소하는 점열

좌표가 음이 아닌 정수인 서로 다른 점 $A_1(x_1, y_1), A_2(x_2, y_2), \ldots, A_n(x_n, y_n)$이 주어진다. 임의의 $i$에 대해 $x_i \le x_{i+1}$이고 $y_i \ge y_{i+1}$이면 이 점열을 감소한다고 한다.

$x_1 + y_1 = a_1, x_2 + y_2 = a_2, \ldots, x_n + y_n = a_n$을 만족하는 감소 점열의 개수를 구하라.

첫 줄에 양의 정수 $n$이 주어진다. 둘째 줄에 $n$개의 음이 아닌 정수 $a_1, a_2, \ldots, a_n$이 주어진다.

조건을 만족하는 점열의 개수를 $123456789$로 나눈 나머지를 출력한다.

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