#include //#include "testlib.h" using namespace std ; #define LL long long int #define ft first #define sd second #define PII pair #define MAXN 200005 #define MAXM 1001 #define mp make_pair #define f_in(st) freopen(st,"r",stdin) #define f_out(st) freopen(st,"w",stdout) //#define sc(x) scanf("%d",&x) //#define scll(x) scanf("%lld",&x) #define sc(x) cin >> x #define scll(x) cin >> x #define pr(x) cout << x << "\n" #define prll(x) cout << x << "\n" //#define pr(x) printf("%d\n",x) //#define prll(x) printf("%lld\n",x) #define all(x) x.begin(),x.end() #define pb push_back #define MOD 1000000000 #define ASST(x,l,r) assert(x >= l && x <= r) int n , m , nCr[4444][4444] , dp2[2222][2222]; 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 ; } void solve(){ sc(n) ; sc(m) ; for(int i=0;i<=n;i++) for(int j=0;j<=m;j++) dp2[i][j] = 0 ; dp2[0][0] = 1 ; for(int i=1;i<=n;i++){ int s = 0 ; for(int j=0;j<=m;j++){ s += dp2[i-1][j] ; if(s >= MOD) s -= MOD ; dp2[i][j] = 1LL * s * nCr[j+m-1][m-1] % MOD ; } } int ans = 0 ; for(int i=0;i<=m;i++){ ans += dp2[n][i] ; if(ans >= MOD) ans -= MOD ; } pr(ans) ; } int main(){ int t ; pre() ; sc(t) ; while(t --){ solve() ; } return 0 ; }