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 non-negative integer. R is called steady if the sum of elements in the ith row is not less then the sum of elements in the (i-1)th row for each i where 2 ≤ i ≤ N and the sum of elements in the Nth 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.
import sys
 
MOD = 1000000000
 
T = int(sys.stdin.readline())
 
 
def gcd(a, b):
 return a if b == 0 else gcd(b, a % b)
 
 
def solve(n, r):
 if r > n - r:
  r = n - r
 
 num = 1
 den = 1
 j = 1
 for i in range(n - r + 1, n + 1):
  num *= i
  den *= j
  j += 1
 
 return (num / den) % MOD
 
for t in range(T):
 n, r = list(map(int, sys.stdin.readline().split()))
 t=r-1
 q=0
 li=[]
 for i in range(r+1):
  li.append(solve(t,q))
  t+=1
  q+=1
 arr=li[:]
 temp=0
 for i in range(1,n):
  summ=sum(arr)
  for j in range(r+1):
   if(j==0):
    summ+=0
   else:
    summ-=temp
   temp=arr[j]
   arr[j]=(li[j]*(summ%MOD))%MOD
 print(sum(arr)%MOD) 
import sys
 
MOD = 1000000000
 
T = int(sys.stdin.readline())
 
 
def gcd(a, b):
 return a if b == 0 else gcd(b, a % b)
 
 
def solve(n, r):
 if r > n - r:
  r = n - r
 
 num = 1
 den = 1
 j = 1
 for i in range(n - r + 1, n + 1):
  num *= i
  den *= j
  j += 1
 
 return (num / den) % MOD
 
for t in range(T):
 n, r = list(map(int, sys.stdin.readline().split()))
 t=r-1
 q=0
 li=[]
 for i in range(r+1):
  li.append(solve(t,q))
  t+=1
  q+=1
 arr=li[:]
 temp=0
 for i in range(1,n):
  summ=sum(arr)
  for j in range(r+1):
   if(j==0):
    summ+=0
   else:
    summ-=temp
   temp=arr[j]
   arr[j]=(li[j]*(summ%MOD))%MOD
 print(sum(arr)%MOD) 