这是一道看起来很困难 *2900 题，但本萌新居然做的很顺利，而且好像我的方法相对比较简单，因此写一篇题解~
题意
求所有满足以下要求的有序数组对 (a,b) 的 a 长度和：
分析
首先第三个条件看起来很怪异难以分析，但结合单调性考虑，可以发现第三个条件相当于不存在下标 i 使得 a_i=a_{i+1} 且 b_i=b_{i+1}。这样看起来好多了。
对于有两个整数数组且数组间存在约束的问题，能较为自然地将其映射到网格图上思考。如果将 (a_i,b_i) 视作网格图上的点，则其必然处于一个 (0,0 ) \rightarrow (n,m) 的只右只上路径上。而且条件三还刚好保证了这些点是不重合的！这侧面印证了这一转化正是出题人所想要的。
一件烦人的事情是 (a,b) 点集和路径都是一对多的关系。例如：若点击为 \{(0,0),(1,1),(1,2)\}。则有两个只右只上路径满足要求：(0,0) \rightarrow (0,1) \rightarrow (1,1) \rightarrow (1,2) 和 (0,0) \rightarrow (1,0) \rightarrow (1,1) \rightarrow (1,2)。 另一边，路径 (0,0) \rightarrow (0,1) \rightarrow (1,1) \rightarrow (1,2) 也对应很多可能的点集：\{(0,0),(1,1),(1,2)\},\{(0,0),(1,2)\} 等。
因此，强行规定一个点集只对应一个路径：对于 (a_i,b_i) 和 (a_{i+1},b_{i+1})，路径必须先向右走到 x=a_{i+1} 后向上走到 y=b_{i+1}。这样一个点集只对应一个路径。
这仍然不能改变一个路径对应多个点集的事实。但考虑一个路径对应哪些点集则是容易的。稍加分析则可发现：
- 一条路径的起点、终点和先上再右的拐点必须位于点集内，其他点则随意。
这是因为，路径连接两个点的方式是先右再上。因此如果出现先上再右的拐点，说明这一定不是在连接两个点，说明这就是一个点所在的位置。
那么如何计算长度呢？最便捷的方法是计算每个点的贡献。如果这个点必须在点集内，则会对总长度有点集方案数的贡献，因为每个点集都必须包含；否则对总长度有点集方案数的一半的贡献，因为有一半的方案它在其中。相加即可。
由于路径长度为 n+m+1，设有 i 个先上再右拐点，则其点集总长度为
因此本题马上就要完成了！对于输入的 $(n,m)$，枚举先右再上拐点数量 $i \in [0,\text{min}(n,m)]$，则拐点有 $C_{i}^{n} C_{i}^{m}$ 种方案，对于每种方案的长度和就是上面那个式子。
时间复杂度为 $O(n)$。
```cpp
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int MAXN=5e6+5,MOD=1e9+7;
int T,N,M;
LL fac[MAXN],ifac[MAXN],po[MAXN*2];
LL QPow(LL base,int po)
{
LL res=1;
while(po)
{
if(po&1) res=res*base%MOD;
base=base*base%MOD;
po>>=1;
}
return res;
}
LL C(int n,int m)
{
return fac[n]*ifac[m]%MOD*ifac[n-m]%MOD;
}
int main()
{
fac[0]=1;
for(int i=1;i<=MAXN-5;i++) fac[i]=fac[i-1]*i%MOD;
ifac[MAXN-5]=QPow(fac[MAXN-5],MOD-2);
for(int i=MAXN-6;i>=0;i--) ifac[i]=ifac[i+1]*(i+1)%MOD;
po[0]=1;
for(int i=1;i<=2*MAXN-5;i++) po[i]=po[i-1]*2%MOD;
scanf("%d",&T);
while(T--)
{
scanf("%d %d",&N,&M);
LL ans=(2ll*po[N+M-1])%MOD;
ans=(ans+1ll*(N+M-1)*po[N+M-2]%MOD)%MOD;
//这里是对于有0个拐点情况的单独计算，但其实也是适用下面的算式的
for(int i=1;i<=min(N,M);i++)
{
LL t=C(N,i)*C(M,i)%MOD;
LL v1=1ll*(i+2)*po[N+M-1-i]%MOD;
LL v2=1ll*(N+M-1-i)*po[N+M-2-i]%MOD;
ans=(ans+t*((v1+v2)%MOD)%MOD)%MOD;
}
printf("%lld\n",ans);
}
return 0;
}
```