题解

思路推导

由于 $a$ 非降、$b$ 非升，条件 $a_i\le b_i$ 中最强的是 $a_m\le b_m$。把两个数组按 $a_1,a_2,\ldots,a_m,b_m,b_{m-1},\ldots,b_1$ 的顺序连接，就得到一个长度为 $2m$、元素取值在 $1$ 到 $n$ 的非降序列。反过来，任意这样的非降序列也唯一对应一对合法数组。

因此问题等价于从 $n$ 种数中可重复地选择 $2m$ 个。按照可重组合计数，答案为 $\binom{n+2m-1}{2m}$。

做法

预处理到 $n+2m$ 的阶乘和逆阶乘，用费马小定理计算阶乘的模逆元，再按组合数公式求值。模数 $10^9+7$ 为质数，并且所需阶乘下标远小于模数。

正确性证明

上述连接操作把任意合法数组对映射为一个长度 $2m$ 的非降序列；条件 $a_m\le b_m$ 保证连接处也非降。逆操作取序列前 $m$ 项作为 $a$，后 $m$ 项逆序作为 $b$，可恢复全部条件。因此这是双射。

长度为 $2m$、从 $n$ 种值中可重复选择的非降序列数量正是 $\binom{n+2m-1}{2m}$，所以算法输出与合法数组对数量相等。

复杂度分析

预处理时间复杂度为 $O(n+m)$，空间复杂度为 $O(n+m)$。