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.

Difficulty: interview

Starter code:

Solutions:
# This is not my code, it's Snehasish Karmakar's.  Refer to http://www.codechef    .com/viewsolution/7153774
# for original version.
# Submitting it to try and work out if it can be sped up.

def compute_nCr(n,r) :
 C[0][0]=1
 for i in range(1,n+1) :
#       print "i",i
  C[i][0]=1
  for j in range(1,min(i,r)+1) :
   if i!=j :
    C[i][j]=(C[i-1][j-1]+C[i-1][j])%MOD
   else :
    C[i][j]=1
  
 
def solve(n,m) :
 store=[C[m+i-1][i] for i in range(m+1)]
 
 for i in range(1,n+1) :
  s=1
  for j in range(1,m+1) :
   s=(s+store[j])%MOD
   store[j]=(s*C[m+j-1][j])%MOD
  #   print "a[%d][%d]=%d"%(i,j,s)
 
 return s 
 
MOD=1000000000
LIMIT=2000
 
C=[[0] * (LIMIT + 1) for _ in range(2*LIMIT+1)]
compute_nCr(2*LIMIT,LIMIT)
t=int(input())
 
while t :
 n,m=list(map(int,input().split()))
 print(solve(n,m))
 t-=1

# This is not my code, it's Snehasish Karmakar's.  Refer to http://www.codechef    .com/viewsolution/7153774
# for original version.
# Submitting it to try and work out if it can be sped up.

def compute_nCr(n,r) :
 C[0][0]=1
 for i in range(1,n+1) :
#       print "i",i
  C[i][0]=1
  for j in range(1,min(i,r)+1) :
   if i!=j :
    C[i][j]=(C[i-1][j-1]+C[i-1][j])%MOD
   else :
    C[i][j]=1
  
 
def solve(n,m) :
 store=[C[m+i-1][i] for i in range(m+1)]
 
 for i in range(1,n+1) :
  s=1
  for j in range(1,m+1) :
   s=(s+store[j])%MOD
   store[j]=(s*C[m+j-1][j])%MOD
  #   print "a[%d][%d]=%d"%(i,j,s)
 
 return s 
 
MOD=1000000000
LIMIT=2000
 
C=[[0 for x in range(LIMIT+1)] for y in range(2*LIMIT+1)]
compute_nCr(2*LIMIT,LIMIT)
t=int(input())
 
while t :
 n,m=list(map(int,input().split()))
 print(solve(n,m))
 t-=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)