Steady tables

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Let's consider a rectangular table R consisting of N rows and M columns. Rows are enumerated from 1 to N from top to bottom. Columns are enumerated from 1 to M from left to right. Each element of R is a nonnegative integer. R is called steady if the sum of elements in the i^{th} row is not less then the sum of elements in the (i1)^{th} row for each i where 2 ≤ i ≤ N and the sum of elements in the N^{th} row is less than or equal to M. Your task is to find the number of different steady tables of size N x M modulo 1 000 000 000.
Input
The first line of input contains a single integer T denoting number of test cases. First and the only line of each test case contains two space separated integers N and M denoting the number of rows and columns respectively.
Output
For each test case, print a single integer corresponding to the answer.
Constraints
 1 ≤ T ≤ 10
 1 ≤ N, M ≤ 2000
Subtasks
 Subtask 1 : 1 ≤ T ≤ 10 , 1 ≤ N,M ≤ 50 : ( 23 pts )
 Subtask 2 : 1 ≤ T ≤ 10 , 1 ≤ N,M ≤ 500 : ( 29 pts )
 Subtask 3 : 1 ≤ T ≤ 10 , 1 ≤ N,M ≤ 2000 : ( 48 pts )
Example
Input: 3 1 1 2 2 2 3 Output: 2 25 273
Explanation
Test case 1 : There are only 2 such grids possible 0 and 1.
Author:  pavel1996 
Editorial  http://discuss.codechef.com/problems/STDYTAB 
Tags  combinatorics, dynamicprogramming, easy, june15, pavel1996 
Date Added:  21092014 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 