题解：
比较水的题目
普通dp其实复杂度还是比较大的
可以任意模数ntt优化。。
但好像没人写。。
代码：
#include <bits/stdc++.h>
using namespace std;
#define rint register int
#define IL inline
#define rep(i,h,t) for (rint i=h;i<=t;i++)
#define dep(i,t,h) for (rint i=t;i>=h;i--)
const int mo=1e9+;
int n,m,f[][];
int main()
{
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
ios::sync_with_stdio(false);
int T;
cin>>T;
while (cin>>n>>m)
{
m++;
/* f[0][0]=1;
rep(i,1,n)
f[1][i]=f[0][i]=1;
rep(i,2,n)
{
rint tmp=min(i,m);
rep(j,1,tmp)
{
rint tmp=0,m1,m2;
rep(k,0,i-1)
{
m1=f[k][j-1]; m2=f[i-k-1][j-1];
if (m1&&m2) tmp=(tmp+1ll*m1*m2)%mo;
}
f[i][j]=tmp;
}
rep(j,min(i,m)+1,max(n,m))
f[i][j]=f[i][j-1];
} */
f[][]=;
rep(i,,n) f[i][]=f[i][]=;
rep(i,,m)
rep(j,,n)
{
rint tmp=;
rep(k,,j-)
{
tmp=(tmp+1ll*f[i-][k]*f[i-][j-k-])%mo;
}
f[i][j]=tmp;
}
cout<<(f[m][n]-f[m-][n]+mo)%mo<<endl;
//cout<<(f[n][m]-f[n][m-1]+mo)%mo<<endl;
}
return ;
}