Nông dân Nhoj đã thả Bessie ở một nơi xa lạ! Tại thời điểm \(t=0\), Bessie ở vị trí \(x=0\) trên một trục số vô hạn. Cô ấy hoảng loạn tìm lối thoát bằng cách di chuyển sang trái hoặc phải \(1\) đơn vị mỗi giây. Tuy nhiên, thực tế là không có lối thoát nào, và sau \(T\) giây, Bessie quay lại \(x=0\), mệt mỏi và chán nản.

Nông dân Nhoj cố gắng theo dõi Bessie nhưng chỉ biết số lần Bessie vượt qua các vị trí \(x=0.5, 1.5, 2.5, \ldots, (N-1).5\), được cho bởi mảng \(A_0, A_1, \dots, A_{N-1}\) (\(1 \leq N \leq 10^5\), \(1 \leq A_i \leq 10^6\)). Bessie không bao giờ đến vị trí \(x>N\) hay \(x<0\).

Cụ thể, lộ trình của Bessie có thể được biểu diễn bằng một chuỗi gồm \(T = \sum_{i=0}^{N-1} A_i\) ký tự 'L' và 'R', trong đó ký tự thứ \(i\) đại diện cho hướng Bessie di chuyển trong giây thứ \(i\). Số lần thay đổi hướng được định nghĩa là số lần xuất hiện của 'LR' cộng với số lần xuất hiện của 'RL'.

Hãy giúp nông dân Nhoj đếm số lộ trình Bessie có thể đã thực hiện phù hợp với mảng \(A\) và tối thiểu hóa số lần thay đổi hướng. Đảm bảo rằng luôn có ít nhất một lộ trình hợp lệ.

Input

• Dòng đầu tiên chứa số nguyên \(N\).
• Dòng thứ hai chứa các số nguyên \(A_0, A_1, \dots, A_{N-1}\).

Output

• In ra số lộ trình Bessie có thể đã thực hiện, modulo \(10^9+7\).

Scoring

• Subtask \(1\): \(N \leq 2\) và \(\max(A_i) \leq 10^3\)
• Subtask \(2\): \(N \leq 2\)
• Subtask \(3\): \(\max(A_i) \leq 10^3\)
• Subtask \(4\): Không có ràng buộc nào khác.

2
4 6

2

RRLRLLRRLL
RRLLRRLRLL