В момент времени \(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\)
с минимальным количеством изменений направления движения. Гарантируется существование
как минимум одного такого маршрута.
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит \(N\). Вторая строка содержит \(A_0,A_1,\dots,A_{N-1}\).
ФОРМАТ ВЫВОДА (на экран / stdout):
Количество маршрутов Беси по модулю \(10^9+7\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
4 6
|
2
|