分析

这题是一个经典的组合数学的题。先说题解的证明我是看不会的，以下给出一个较为简便的理解。先说明不下降和不上升子序列没有本质区别，只需要讨论一种即可。

简化问题

给你一个长度为 的序列，要求每个元素 ，求不下降子序列的方案数。先考虑到对于一个一个集合 一定只对应一个序列。那么我们转化一下 表示 这个数在集合中出现的次数，那么 就可以表示一个序列，其中 。现在就是求问这个集合有多少种方案。这个可以考虑插板法，现在等同于给你 一个长度为 元素全为的 的序列，两个板之间的 的个数就是 的大小。因为左右两个端点必须有个板的。所以 。可以看作 个位置中要挑出 个 的方案数。

原问题

这个问题其实和上面的问题没有本质区别，只需要考虑上限是谁，枚举上限，再枚举前一部分选多少个之后，根据范德蒙德卷积公式化简，可得 。只需要预处理阶乘的逆元就好了，时间复杂度为 。

代码

#include<bits/stdc++.h>
using namespace std;
#define LL long long
LL read() {
    LL x = 0,f = 0;char ch = getchar();
    while(!isdigit(ch)) {if(ch=='-')f=1;ch = getchar();}
    while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
    return f ? -x : x; 
} 
const int N = 2e7 + 100,M = 1e7,P = 1e9 + 7;
int qpow(int a,int b) {
    LL x = 1;for(;b;b>>=1,a=1LL*a*a%P) 
    if(b&1) x = 1LL *  x * a % P;return x;
}
int n,m,pre[N],inv[N];
int C(int a,int b) {return 1LL * pre[b] * inv[a] % P * inv[b-a] % P;}
int main()
{
    pre[0] = 1;
    for(int i = 1;i <= 2*M+1;i++) pre[i] = 1LL * pre[i-1] * i % P;
    inv[2*M+1] = qpow(pre[2*M+1],P-2);
    for(int i = 2*M;i >= 0;i--) inv[i] = 1LL * inv[i+1] * (i + 1) % P;
    int T = read();
    while(T--) {
        n = read();m = read();
        LL ans = 0;
        for(int i = 0;i < n;i++) {
            ans = (1LL * ans + C(m-1,m+2*i-1)) % P;
        }
        printf("%lld\n",ans);
    }
    return 0;
}