У час \(t=0\), Бесі перебуває у точці \(x=0\) на нескінченної числової прямий. Вона рухається на \(1\) ліворуч або праворуч кожну секунду. Рівно через \(T\) секунд вона повертається до точки \(x=0\).

Фермер Джон знає, скільки разів Бесі перетинала точки \(x=.5, 1.5, 2.5, \ldots, (N-1).5\), і це задається масивом \(A_0,A_1,\dots,A_{N-1}\) (\(1\leq N \leq 10^5\), \(1 \leq A_i \leq 10^6\)). Бесі ніколи не досягне ні \(x>N\), ні \(x<0\).

Зокрема маршрут Бесі може бути представлений рядком \(T = \sum_{i=0}^{N-1} A_i\) символів \(L\) і \(R\), де \(i\)-ий символ представляє напрямок, у якому рухалася Бесі протягом \(i\)-ої секунди. Кількість змін напряму визначається як кількість пар символів \(LR\) плюс кількість пар символів \(RL\) у цьому рядку.

Допоможіть ФД порахувати кількість маршрутів, що відповідають масиву \(A\) з мінімальною кількістю змін напряму руху. Гарантується існування щонайменше одного такого маршруту.

Формат вхідних даних

Перший рядок містить \(N\). Другий рядок містить \(A_0,A_1,\dots,A_{N-1}\).

Формат вихідних даних

Кількість маршрутів Бесі по модулю \(10^9+7\).

Приклад вхідних даних

2
4 6

Приклад вихідних даних

2

Бесі може змінити напрямок не менше 5 разів. Існує два маршруту з 5 змінами напряму:

RRLRLLRRLL
RRLLRRLRLL

ОЦІНЮВАННЯ:

• Тести 2-4: \(N\le 2\) and \(\max(A_i)\le 10^3\)
• Тести 5-7: \(N\le 2\)
• Тести 8-11: \(\max(A_i)\le 10^3\)
• Тести 12-21: Немає додаткових обмежень.