参考了这篇博客
引入
\(n\) 个元素进栈序列为：\(1,2,3,4...n\)，求总共有多少种出栈序列。
将进栈表示为 \(+1\)，出栈表示为 \(-1\)，则 \(1,3,2\) 的出栈序列可以表示为：\(+1,-1,+1,+1,-1,-1\)。
根据栈本身的特点，每个出栈序列的所有前缀和必然 \(\geq 0\)，并且最终 \(+1\) 的数量等于 \(-1\) 的数量。
对于这样的问题，总的方案数就被称之为卡特兰数。
表达式
对于卡特兰数，有通项公式： \(C_n=C_{2n}^{n}-C_{2n}^{n+1}=\frac{C_{2n}^{n}}{n+1}\)。
同时也满足以下递推式： \(C_n=C_{n-1} \frac{4n-2}{n+1}\)。
[应用]骗我呢
给定 \(n,m\)，求有多少个 \(n \times m\) 的矩阵，满足：
对于任意的 \(i,j\)，都满足矩阵中第 \(i\) 行第 \(j\) 列的元素 \(x_{i,j}\) 有：
1.\(x_{i,j}<x_{i,j+1} (j<m)\)；
2.\(x_{i,j}<x_{i-1.j-1}\);
3.\(0 \leq x_{i,j} \leq m\)。
结果对 \(10^9+7\) 取模，\(1 \leq n,m \leq 10^6\)。
思路：
注意到矩阵的每一行中有 \(m\) 个元素，一共有 \(0 \sim m\) 共 \(m+1\) 种取值，那么每一行有且仅有一个数不会被取到。
设 \(f_{i,j}\) 表示考虑到第 \(i\) 行，当前这一行不选 \(j\) 这个数的总方案。
考虑当前这一行不选 \(j\)，前一行不选 \(k\)，那么当 \(k>j+1\) 的时候，就会满足 \(x_{i,j+1}=x_{i-1,j+2}=j+1\)，不满足第二条性质，于是就有 \(k \leq j+1\)，那么就有 \(f_{i,j}=\sum_{k=0}^{j+1} f_{i-1,k}\)。
优化一下，可以得到：\(f_{i,j}=\sum_{k=0}^{j} f_{i-1,k}+f_{i-1,j+1}=f_{i,j-1}+f_{i-1,j+1}\)。
那么最终的答案就是 \(\sum_{j=0}^{m} f_{n,i}=f{n+1,m}\)。
考虑将 \(f_{i,j}\) 的递推关系映射到直角坐标系上。（图片源于这篇博客）
不难发现，此时的答案就转化为了从 \((1,0)\) 走到 \((n+1,m)\) 的总方案数。
将第 \(2\) 行到第 \(n+1\) 行的点横坐标 \(+1\)，可以得到：
此时的答案仍然是从 \((1,0)\) 走到 \((n+m+1,m)\) 的总方案数。
将起点平移到坐标原点 \((0,0)\)，在点的两侧分别画出一条直线：
此时的方案数就是从 \((0,0)\) 出发，只能向上或向右走，且不能触屏到 \(A:y=x+1\) 和 \(B:y=x-m-2\) 这两条直线，最终走到 \((n+m+1,m)\) 点的总方案数。
假如不考虑直线的限制，那么答案就是 \(\binom{n+2m+1}{m}\)。
定义一个仅由 \(A,B\) 构成的字符串，如 \(AABBA\)，表示这条路径先穿过了两次 \(A\) 直线，再穿过两次 \(B\) 直线，最后又穿过一次 \(A\) 直线到达终点，不难发现，同一条直线连续经过多次在计算的时候没有影响，所以把相同的部分合并为一次。最终的答案要分别减去以 \(A\) 开头的路径和以 \(B\) 开头的路径。
考虑将直线 \(B\) 关于直线 \(A\) 对称，那么对称过去后的方案数就可以通过组合数直接进行计算，同时也需要注意容斥减去重复的方案数。总的时间复杂度为 \(O(n)\)。
code：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int M=3e6+10,mod=1e9+7;
int n,m,fac[M],infac[M],inv[M];
void init()
{
fac[0]=infac[0]=fac[1]=infac[1]=inv[0]=inv[1]=1;
for(int i=2;i<M;i++) fac[i]=1ll*fac[i-1]*i%mod;
for(int i=2;i<M;i++) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
for(int i=2;i<M;i++) infac[i]=1ll*infac[i-1]*inv[i]%mod;
}
int C(int n,int m){if(n<0||m<0||n<m) return 0;return 1ll*fac[n]*infac[m]%mod*infac[n-m]%mod;}
int calc(int x,int y,int dir)
{
if(x<0||y<0) return 0;int delta=dir?-m-2:1;
return (C(x+y,y)-calc(y+delta,x-delta,dir^1)+mod)%mod;
}
void add(int &a,int b){a+=b;if(a>=mod) a-=mod;}
int main()
{
scanf("%d%d",&n,&m);init();int ans=C(2*n+m+1,n);
ans=(ans-calc(n-1,n+m+2,0)+mod)%mod;
ans=(ans-calc(n+m+2,n-1,1)+mod)%mod;
printf("%d\n",ans);
}