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.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Combinatorics

Mathematics


Solutions:
def compute_nCr(n, r):
	C[0][0] = 1
	for i in range(1, n + 1):
		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
	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


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
if sys.version_info > (3,):
	long = int
	xrange = range

def choose(n, k):
	ntok = 1
	ktok = 1
	for t in xrange(1, min(k, n - k) + 1):
		ntok *= n
		ktok *= t
		n -= 1
	return ntok // ktok

def C(X, M):
	return choose(X + M - 1, M - 1)
import numpy as np

def R(N, M):
	Base = [C(0, M)]
	for i in range(1, M + 1):
		Base.append(Base[i - 1] * (M + i - 1) // i)
	Base = np.array([i % 1000000000 for i in Base], dtype=np.int64)
	Next = Base[:]
	for i in range(1, N):
		Next = np.multiply(Base, np.cumsum(Next) % 1000000000, dtype=np.int64) % 1000000000
	return sum((i for i in Next)) % 1000000000
T = int(input())
for i in range(T):
	(N, M) = list(map(int, input().split()))
	print(R(N, M))