Moo Route (Gold)

Bessie bắt đầu tại vị trí $x=0$ trên trục số. Trong $T$ giây, mỗi giây cô di chuyển sang trái hoặc phải 1 đơn vị, và cuối cùng quay về $x=0$. Cô không bao giờ đi xuống dưới $x=0$ hoặc vượt quá $x=N$.

Mảng $A$ ghi lại số lần Bessie đi qua: $A_0,A_1,\dots ,A_{N-1}$ lần lượt là số lần đi qua $x=0.5,1.5,\dots ,(N-1)\mathrm{.5}$.

Đổi hướng xảy ra tại mỗi cặp "LR" hoặc "RL". Hãy đếm số đường đi hợp lệ có số lần đổi hướng tối thiểu, modulo ${10}^9+7$.

Dữ liệu vào

• Dòng đầu: số nguyên $N$ ($1\le N\le {10}^5$)
• Dòng thứ hai: $N$ số nguyên $A_0,A_1,\dots ,A_{N-1}$ ($1\le A_i\le {10}^6$)

Dữ liệu ra

Số đường đi có số lần đổi hướng tối thiểu, modulo ${10}^9+7$.

Ràng buộc

• $1\le N\le {10}^5$
• $1\le A_i\le {10}^6$

Ví dụ