P9018 [USACO23JAN] Moo Route G

题目描述

现在有一条数轴，$t$ 表示当前时刻。在 $t=0$ 时 Bessie 恰好处在 $x=0$ 的位置。

接下来，每秒钟 Bessie 会向左或者向右移动一个单位距离，我们保证 Bessie 是在 $0-N$ 的位置之间移动并最终停在 $x=0$ 的位置。同时，我们有一个 $A_0,A_1,A_2\ldots A_{N-1}$ 的数列，分别表示 Bessie 经过 $0.5,1.5,2.5\ldots (N-1).5$ 这些点的次数。我们可以用一个由 $\text{L}$ 和 $\text{R}$ 组成的序列来表示 Bessie 的路径，我们称 Bessie 改变了一次方向为在序列中的相邻两个字符不同。现在我们不知道具体的移动序列是什么，但我们知道 Bessie 采用了让她改变方向次数最少的走法。现在请问 Bessie 的路径有多少种不同的可能情况？（我们称两条路径不同当且仅当这条路径对应序列中的某一位不同）

输入格式

第一行一个正整数表示 $N$。

接下来一行有 $N$ 个用空格分隔的正整数表示 $A_0,A_1,A_2\ldots A_{N-1}$。

输出格式

一行一个整数表示结果总数。由于这个值可能很大，请输出其对 $10^9+7$ 取模的结果。

输入输出样例 1

2
4 6

2

说明/提示

$N\le10^5,\max(A_i)\le10^6$。

对于测试点 $2-4$，满足 $N\le2,\max(A_i)\le10^3$。

对于测试点 $5-7$，满足 $N\le2$。

对于测试点 $8-11$，满足 $\max(A_i)\le10^3$。