3858. [USACO23 Jan Gold] Moo Route

【题目描述】

贝茜位于一个一维数轴的 $x=0$ 处。

贝茜需要按要求进行移动，所有要求如下：

$\bullet$ 贝茜每次向左或向右移动 $1$ 个单位距离。

$\bullet$ 贝茜不能到达 $x<0$ 以及 $x>N$ 的区域。

$\bullet$ 给定一个长度为 $N$ 的正整数数组 $A_0,A_1,…,A_{N−1}$。对于 $0≤i≤N−1$，整个移动过程中，贝茜穿过 $x=i+0.5$ 的次数应恰好等于 $A_i$。

$\bullet$ 所有移动结束后，贝茜回到 $x=0$。

$\bullet$ 满足上述所有要求的前提下，整个移动过程中，贝茜转向（连续两次移动的方向不一样，视为转向）的次数尽可能少。

请问，一共有多少个符合所有要求的移动方案，输出对 $10^9+7$ 取模后的结果。

提示：贝茜的移动次数应等于：$\sum_{i=0}^{N-1}A_i$

【输入格式】

第一行包含整数 $N$。

第二行包含 $A_0,A_1,…,A_{N−1}$。

【输出格式】

一个整数，表示符合所有要求的方案数量对 $10^9+7$ 取模后的结果。

【样例1输入】

2
4 6

【样例1输出】

2

【样例1解释】

贝茜在整个移动过程中至少需要转向 $5$ 次，用 $L$ 表示一次向左移动，用 $R$ 表示一次向右移动，满足所有要求的移动方案共有 $2$种：

$RRLRLLRRLL$ 和 $RRLLRRLRLL$

【样例2/3】

点击下载样例2/3

【数据规模与约定】

测试点 $2\sim4$: $N≤2\ ，\ max(A_i)≤10^3$.

测试点 $5\sim7$: $N≤2$.

测试点 $8\sim11$: $max(A_i)≤10^3$.

$100\%$ 测试点: $1≤N≤10^5 , 1≤A_i≤10^6$.