#include <iostream>
using namespace std;
#define mod 1000000000
int nCr[4444][4444];
void pre(){
for(int i=0;i<=4000;i++)
nCr[i][0] = 1 ;
for(int i=1;i<=4000;i++)
for(int j=1;j<=i;j++)
nCr[i][j] = ( nCr[i-1][j-1] + nCr[i-1][j] ) % mod ;
}
long long f(int sum, int m) //returns number of ways to arrange m values such that sum is sum
{ // sum is n, m is k, ans is n+k-1Ck-1
//old code
//if(sum==0)return 1;
//if(sum==1) return m;
//long long ans=m;
//for(int i=2; i<=sum; i++) { ans*=((m+i-1.0)/(sum-i+2)); ans%=mod; }
//return ans;
//NEW CODE
return nCr[sum+m-1][m-1];
}
long long array[2500][2500]; //dp solution
long long temp[2500][2500]; //dp solution builder helper - stores cumulative of values in 'array'
long long sum;
int main()
{
pre();
ios_base::sync_with_stdio(false);
int t, n, m;
cin>>t;
while(t--)
{
cin>>n>>m;
sum=0;
array[0][0] = 1; //f(0,m);
temp[0][0] = 1; //array[0];
for(int i=1; i<=m; i++)
{
array[0][i] = f(i,m)%mod;
temp[0][i] = (temp[0][i-1] + array[0][i])%mod;
//cout<<array[0][i]<<" "<<temp[0][i]<<" -- ";
}
for(int i=1; i<n; i++) //for n rows
{
for(int j=0; j<=m; j++)
{
array[i][j] = (array[0][j]*temp[i-1][j])%mod;
// cout<<array[i][j]<<" ";
if(j==0) temp[i][j]=1;
else temp[i][j] = (temp[i][j-1] + array[i][j])%mod;
}
}
for(int i=0; i<=m; i++) { sum+=(array[n-1][i]); sum%=mod;}
cout<<sum<<"\n";
}
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwojZGVmaW5lIG1vZCAxMDAwMDAwMDAwCgppbnQgbkNyWzQ0NDRdWzQ0NDRdOwogCnZvaWQgcHJlKCl7CiAgICBmb3IoaW50IGk9MDtpPD00MDAwO2krKykKICAgICAgICBuQ3JbaV1bMF0gPSAxIDsKICAgIGZvcihpbnQgaT0xO2k8PTQwMDA7aSsrKQogICAgICAgIGZvcihpbnQgaj0xO2o8PWk7aisrKQogICAgICAgICAgICBuQ3JbaV1bal0gPSAoIG5DcltpLTFdW2otMV0gKyBuQ3JbaS0xXVtqXSApICUgbW9kIDsKfQoKbG9uZyBsb25nIGYoaW50IHN1bSwgaW50IG0pICAvL3JldHVybnMgbnVtYmVyIG9mIHdheXMgdG8gYXJyYW5nZSBtIHZhbHVlcyBzdWNoIHRoYXQgc3VtIGlzIHN1bQp7ICAvLyBzdW0gaXMgbiwgbSBpcyBrLCBhbnMgaXMgbitrLTFDay0xCgkvL29sZCBjb2RlCgkvL2lmKHN1bT09MClyZXR1cm4gMTsKCS8vaWYoc3VtPT0xKSByZXR1cm4gbTsKCS8vbG9uZyBsb25nIGFucz1tOwoJLy9mb3IoaW50IGk9MjsgaTw9c3VtOyBpKyspICB7IGFucyo9KChtK2ktMS4wKS8oc3VtLWkrMikpOyAgYW5zJT1tb2Q7IH0KCS8vcmV0dXJuIGFuczsKCS8vTkVXIENPREUKCXJldHVybiBuQ3Jbc3VtK20tMV1bbS0xXTsKfQoKCmxvbmcgbG9uZyBhcnJheVsyNTAwXVsyNTAwXTsgIC8vZHAgc29sdXRpb24KbG9uZyBsb25nIHRlbXBbMjUwMF1bMjUwMF07ICAvL2RwIHNvbHV0aW9uIGJ1aWxkZXIgaGVscGVyIC0gc3RvcmVzIGN1bXVsYXRpdmUgb2YgdmFsdWVzIGluICdhcnJheScKbG9uZyBsb25nIHN1bTsKCmludCBtYWluKCkgCnsJCglwcmUoKTsKCQoJaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbyhmYWxzZSk7CglpbnQgdCwgbiwgbTsKCWNpbj4+dDsKCXdoaWxlKHQtLSkKCXsKCQljaW4+Pm4+Pm07CgkJc3VtPTA7CgkJCgkJYXJyYXlbMF1bMF0gPSAxOyAgLy9mKDAsbSk7CgkJdGVtcFswXVswXSA9IDE7ICAvL2FycmF5WzBdOwoJCQoJCWZvcihpbnQgaT0xOyBpPD1tOyBpKyspCgkJewoJCQlhcnJheVswXVtpXSA9IGYoaSxtKSVtb2Q7CgkJCXRlbXBbMF1baV0gPSAodGVtcFswXVtpLTFdICsgYXJyYXlbMF1baV0pJW1vZDsKCQkJLy9jb3V0PDxhcnJheVswXVtpXTw8IiAiPDx0ZW1wWzBdW2ldPDwiIC0tICI7CgkJfQoJCQoJCWZvcihpbnQgaT0xOyBpPG47IGkrKykgIC8vZm9yIG4gcm93cwoJCXsKCQkJZm9yKGludCBqPTA7IGo8PW07IGorKykKCQkJewoJCQkJYXJyYXlbaV1bal0gPSAoYXJyYXlbMF1bal0qdGVtcFtpLTFdW2pdKSVtb2Q7CgkJCS8vCWNvdXQ8PGFycmF5W2ldW2pdPDwiICI7CgkJCQlpZihqPT0wKSB0ZW1wW2ldW2pdPTE7CgkJCQllbHNlIHRlbXBbaV1bal0gPSAodGVtcFtpXVtqLTFdICsgYXJyYXlbaV1bal0pJW1vZDsKCQkJfQoJCX0KCQkKCQlmb3IoaW50IGk9MDsgaTw9bTsgaSsrKSB7IHN1bSs9KGFycmF5W24tMV1baV0pOyBzdW0lPW1vZDt9CgkJY291dDw8c3VtPDwiXG4iOwoJfQoJcmV0dXJuIDA7Cn0K