题意：求n个1，m个-1组成的所有序列中，最大前缀之和。
首先引出这样一个问题：使用n个左括号和m个右括号，组成的合法的括号匹配（每个右括号都有对应的左括号和它匹配）的数目是多少？
1.当n=m时，显然答案为卡特兰数$C_{2n}^{n}-C_{2n}^{n+1}$
2.当n<m时，无论如何都不合法，答案为0
3.当n>m时，答案为$C_{n+m}^{n}-C_{n+m}^{n+1}$，这是一个推论，证明过程有点抽象，方法是把不合法的方案数等价于从(0,-2)移动到(n+m,n-m)的方案数，详见https://blog.****.net/x_1023/article/details/78290683
回到题目，如果把1看成右括号，把-1看成左括号，那么最大前缀和为0相当于匹配合法，就是上面讨论的第三种情况。
如果进一步扩展，最大前缀和为1,2,3,...,k的情况该如何处理呢？
考虑最大前缀和大于等于k的情况，其实根据上面的方法，可以等价于从点(0,-2k)走到点(n+m,n-m)的方案数，即$C_{n+m}^{n+k}$，前提是$max(m-n,0)\leqslant k\leqslant m$，然后差分一下就能得到最大前缀和等于k时的方案数了。复杂度$O(n+m)$。由于题目中的n和m分别代表右括号和左括号，所以n和m要反过来。
自己的组合数学真是太辣鸡了，还是要提高一下姿势水平~
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=+,mod=;
int n,m,inv[N],f[N],invf[N],ans[N];
int C(int n,int m) {return n<m?:(ll)f[n]*invf[m]%mod*invf[n-m]%mod;}
int main() {
inv[]=f[]=invf[]=;
for(int i=; i<N; ++i)inv[i]=(ll)(mod-mod/i)*inv[mod%i]%mod;
for(int i=; i<N; ++i)f[i]=(ll)f[i-]*i%mod,invf[i]=(ll)invf[i-]*inv[i]%mod;
scanf("%d%d",&n,&m);
for(int i=max(n-m,); i<=n; ++i)ans[i]=C(n+m,m+i);
for(int i=max(n-m,); i<n; ++i)ans[i]=(ans[i]-ans[i+]+mod)%mod;
int sum=;
for(int i=max(n-m,); i<=n; ++i)sum=(sum+(ll)i*ans[i]%mod)%mod;
printf("%d\n",sum);
return ;
}