不在沉默中躺平，就在喧嚣中躺平。
但谁说人一定要躺平？我要 work work work work work work work work
勤劳又勇敢的 XSC062 为了 OI 的关键杂题集 她付出了巨大的贡献 巨大的牺牲
巨大的 carry 无敌了 无敌了 
[USACO23JAN] Moo Route G
https://www.luogu.com.cn/problem/P9018
希望大家不要和我一样忽略了重要条件：终点也是 \(0\)。这意味着每个点都会被左右成对地经过，那么不妨令 \(A_i\gets \frac 2{A_i}\)。
观察到给了 \(N=2\) 的一档分，考虑该情况。
若 \(A_1> A_2\)：
此时最优策略为……
|---------> <---------| |---------> <---------| |---------> <---------| |----> <----| |----> <----| =========== 0 1 2只要不拆开一组，箭头排列顺序任意。显然方案数为 \({A_1}\choose {A_2}\)。
Otherwise：
此时最优策略为……
|----------> <----| |----> <----| |----> <---------| |---------> <---------| =========== 0 1 2相似地，只要不拆开一组，箭头排列顺序任意，可以注意到除了第一个，每个长
|--->的前面一定是一个长<---|，那么问题转化为选择 \(A_1-1\) 个短<---|拉长，方案数为 \({A_2-1}\choose{A_1-1}\)。
进一步，考虑 \(N=3\) 的情况。若已知子问题 \(0\to1\to2\) 的方案和子问题 \(1\to2\to3\) 的方案，可以直接乘起来合并。为什么呢？
二者经过 \(2\) 的次数相等；在子问题 \(0\to1\to2\) 中，\(1\to2\) 的下一步一定是 \(2\to 1\)；我们把该过程替换为子问题 \(1\to 2\to 3\) 中对应的一段 \(1\to2\to\cdots\to2\to1\) 的路径即可。
那么两两合并起来，可以得到最终答案为 \(\prod\limits_{i=1}^{n-1}\begin{cases}{\binom{A_i}{A_{i+1}}}&A_i>A_{i+1}\\{\binom{A_{i+1}-1}{A_i-1}}&\text{otherwise}\end{cases}\)。
#include <bits/stdc++.h>
const int lim = 5e5;
const int mod = 1e9 + 7;
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int n;
std::cin >> n;
std::vector<int> a(n + 1);
for (int i = 1; i <= n; ++i)
std::cin >> a[i], a[i] /= 2;
std::vector<long long> inv(lim + 1), fac(lim + 1);
auto qkp = [&](long long x, int y) {
long long res = 1ll;
for (; y; (x *= x) %= mod, y >>= 1)
if (y & 1)
(res *= x) %= mod;
return res;
};
inv[0] = fac[0] = 1ll;
for (int i = 1; i <= lim; ++i)
fac[i] = fac[i - 1] * i % mod;
inv[lim] = qkp(fac[lim], mod - 2);
for (int i = lim - 1; i; --i)
inv[i] = inv[i + 1] * (i + 1) % mod;
auto C = [&](int n, int m) {
return fac[n] * inv[n - m] % mod * inv[m] % mod;
};
long long res = 1ll;
for (int i = 1; i < n; ++i)
if (a[i] > a[i + 1])
(res *= C(a[i], a[i + 1])) %= mod;
else
(res *= C(a[i + 1] - 1, a[i] - 1)) %= mod;
std::cout << res << '\n';
return 0;
}