Jim is doing his discrete maths homework which requires him to repeatedly calculate ^{n}C_{r}(n choose r) for different values of n. Knowing that this is time consuming, he goes to his sister June for help. June,  being a computer science student knows how to convert this into a computer program and generate the answers quickly. She tells him, by storing the lower values of ^{n}C_{r}(n choose r), one can calculate the higher values using a very simple formula. 

If you are June, how will you calculate ^{n}C_{r} values for different values of n?

Since ${}^{n}C_{r}$values will be large you have to calculate them modulo $\mathbf{10^{9}}$.  

Input Format 

The first line contains the number of test cases T. 

T lines follow each containing an integer n. 

Output Format 

For each n output the list of ^{n}C_{0} to ^{n}C_{n} each separated by a single space in a new line. If the number is large, print only the last 9 digits. i.e. modulo 10^{9}

Constraints 

1<=T<=200 

1<=n< 1000

Sample Input

3
2
4
5

Sample Output

1 2 1
1 4 6 4 1
1 5 10 10 5 1

Explanation 

For 2 we can check ^{2}C_{0}  ^{2}C_{1} and ^{2}C_{2} are 1, 2 and 1 respectively. The other inputs' answer follow similar pattern.

Source: hackerrank | Difficulty: MEDIUM
Tags: Combinatorics


Solutions:
from math import ceil
T = int(input())
while T > 0:
	T -= 1
	N = int(input())
	temp = 1
	print(1, end=' ')
	for i in range(1, N + 1):
		temp = temp * (N - i + 1) // i
		print(temp % 10 ** 9, end=' ')
	print('')


t = int(input())
for i in range(t):
	n = int(input())
	li = [1]
	for r in range(1, n + 1):
		li.append(li[-1] * (n - r + 1) // r)
		li[-2] %= 1000000000
	print(*li)


import math
f = math.factorial
n = int(input())
for x in range(0, n):
	a = int(input())
	res = []
	for b in range(0, int((a - a % 2) / 2) + 1):
		res.append(f(a) // (f(b) * f(a - b)) % 1000000000)
	for x in (c for d in (range(1, len(res) + a % 2), range(len(res), 0, -1)) for c in d):
		print(int(res[x - 1]), end=' ')
	print('')


t = int(input())
N = [int(input()) for _ in range(0, t)]
m = max(N)
triangle = [[1]]
for i in range(0, m):
	current = triangle[i]
	offset = [0]
	next = [(x + y) % 10 ** 9 for (x, y) in zip(offset + current, current + offset)]
	triangle.append(next)
for n in N:
	print(' '.join(map(str, triangle[n])))


rem = 10 ** 9
T = int(input())
vals = []
maxVal = 0
for i in range(T):
	vals.append(int(input()))
	if vals[i] > maxVal:
		maxVal = vals[i]
comb = [[1, 1]]
for i in range(1, maxVal):
	comb.append([1])
	for j in range(i):
		comb[i].append((comb[i - 1][j] + comb[i - 1][j + 1]) % rem)
	comb[i].append(1)
for i in vals:
	for j in comb[i - 1]:
		print(j, end=' ')
	print()


comb_cache = {}

def comb(n, r):
	cnr = comb_cache.get((n, r), None)
	if cnr:
		return cnr
	if r == 0:
		return 1
	elif r == 1:
		return n
	elif r > int(n / 2):
		return comb(n, n - r)
	else:
		comb_cache[n, r] = comb(n - 1, r) + comb(n - 1, r - 1)
		return comb_cache[n, r]
T = int(input().strip())
for _ in range(T):
	n = int(input().strip())
	for k in range(n + 1):
		print(comb(n, k) % 10 ** 9, end=' ')
	print()


def main():
	matrix = 1001 * [None]
	for i in range(1001):
		matrix[i] = (i + 1) * [None]
	matrix[0][0] = 1
	matrix[1][0] = 1
	matrix[1][1] = 1
	for i in range(1001):
		for j in range(i + 1):
			if j == 0:
				matrix[i][j] = 1
			elif j == i:
				matrix[i][j] = 1
			else:
				matrix[i][j] = matrix[i - 1][j] + matrix[i - 1][j - 1]
	t = int(input())
	for i in range(t):
		s = ''
		n = int(input())
		for j in range(n + 1):
			s = s + str(matrix[n][j] % 1000000000) + ' '
		print(s)
main()


t = input()
l = []
for i in range(int(t)):
	n = input()
	l.append(int(n))
	s = []
	k = [1, 1]
	s.append(k)
for i in range(max(l) - 1):
	h = [1]
	for j in range(len(s[i]) - 1):
		z = s[i][j] + s[i][j + 1]
		if z > 1000000000:
			z = z % 1000000000
		h.append(z)
	h.append(1)
	s.append(h)
for i in l:
	if i == 1:
		print('1 1')
	else:
		for k in s[i - 1]:
			print(k, end=' ')
		print()


T = int(input())
t = [[1, 1]]
for i in range(1000):
	l = len(t[i])
	row = [1] + [(a + b) % 1000000000 for (a, b) in zip(t[i][:l - 1], t[i][1:])] + [1]
	t.append(row)
for i in range(T):
	N = int(input())
	print(' '.join(map(str, t[N - 1])))


import sys
from functools import reduce

def simple_factorial(n):
	if n == 0:
		return 1
	else:
		return reduce(lambda x, y: x * y, range(1, n + 1))

def factorial_using_gamma(n):
	pass

def generate_k_combinations(n):
	result = [1, n]
	if n == 1:
		return result
	if n == 2:
		return result + [1]
	n_factorial = simple_factorial(n)
	index_median = (n + 1) // 2
	for k in range(2, index_median):
		nCk = n_factorial // (simple_factorial(n - k) * simple_factorial(k))
		result.append(nCk)
	if n % 2 == 0:
		median_value = simple_factorial(n // 2)
		nCk = n_factorial // (median_value * median_value)
		result.append(nCk)
		result += result[index_median - 1::-1]
	else:
		result += result[index_median::-1]
	return result
number_of_test_cases = int(sys.stdin.readline())
if not 1 <= number_of_test_cases <= 200:
	raise ValueError('Invalid number of test cases.')
for test in range(number_of_test_cases):
	n = int(sys.stdin.readline())
	if 1 <= n < 1000:
		k_combinations = generate_k_combinations(n)
		output = ' '.join(('{}'.format(k % 10 ** 9) for k in k_combinations))
		print(output)
	else:
		raise ValueError('N out of range.')


T = int(input())
for t in range(0, T):
	N = int(input())
	Cs = [1]
	for k in range(0, N):
		Cs.append(Cs[-1] * (N - k) // (k + 1))
	print(' '.join([str(x % 10 ** 9) for x in Cs]))


input_row1 = input('')
N = int(input_row1)
for i in range(N):
	n = int(input(''))
	comb_list = ['1']
	comb = 1
	for j in range(n):
		comb = comb * (n - j) // (j + 1)
		comb_list.append(str(comb % 1000000000))
	print(' '.join(comb_list))


import sys
T = int(sys.stdin.readline())
pascal = [[1], [1, 1]]
for _ in range(T):
	n = int(sys.stdin.readline())
	while n >= len(pascal):
		pascal.append([1] + [(pascal[-1][i] + pascal[-1][i + 1]) % 10 ** 9 for i in range(len(pascal) - 1)] + [1])
	print(*pascal[n], sep=' ')


x = int(input())
for i in range(x):
	num = int(input())
	j = num // 2 + 1
	lis = []
	for choice in range(j):
		c = 1
		for mult in range(num, num - choice, -1):
			c = c * mult
		for q in range(1, choice + 1):
			c = c // q
		lis.append(c % 1000000000)
	for (i, numb) in enumerate(lis):
		lis[i] = str(numb)
	if num % 2 == 0:
		print(' '.join(lis + lis[-2::-1]))
	else:
		print(' '.join(lis + lis[::-1]))


class table:

	def __init__(self):
		self.table = [[], [1]]
		self.length = 1

	def __getitem__(self, index):
		for i in range(self.length, index):
			self.table.append([1] + [(self.table[i][j] + self.table[i][j + 1]) % 10 ** 9 for j in range(i - 1)] + [1])
			self.length += 1
		return self.table[index]
import sys
next(sys.stdin)
fibonacci = table()
for line in sys.stdin:
	print(' '.join(map(str, fibonacci[int(line.strip()) + 1])))


t = int(input())
for i in range(t):
	n = int(input())
	cs = [1]
	for j in range(1, n + 1):
		cs = [1] + [(cs[k - 1] + cs[k]) % 10 ** 9 for k in range(1, j)] + [1]
	print(' '.join(map(str, cs)))


import sys

def pascal(n):
	row = [1]
	k = [0]
	for x in range(max(n, 0)):
		row = [l + r for (l, r) in zip(row + k, k + row)]
	return row

def main():
	t = int(sys.stdin.readline())
	for _ in range(t):
		n = int(sys.stdin.readline())
		for x in pascal(n):
			print(x % 10 ** 9, end=' ')
		print()
main()


C = []
T = int(input())
for t in range(T):
	n = int(input())
	for i in range(len(C), n + 1):
		Ccur = []
		C.append(Ccur)
		for j in range(i + 1):
			r = 1
			if 0 < j < i:
				r = C[i - 1][j - 1] + C[i - 1][j]
			Ccur.append(r)
	print(' '.join([str(v % 10 ** 9) for v in C[n]]))


numtests = int(input())
tests = [int(input()) for x in range(numtests)]
item = [[1]]
for x in range(1, 1000):
	new = []
	previous = item[x - 1]
	k = len(previous) + 1
	for i in range(k):
		j = i - 1
		t = i
		if j < 0:
			prev = 0
			next = previous[t]
		elif t > len(previous) - 1:
			next = 0
			prev = previous[j]
		else:
			prev = previous[j]
			next = previous[t]
		new.append((prev + next) % 1000000000)
	item.append(new)
for x in tests:
	a = [str(i) for i in item[x]]
	print(' '.join(a))


T = int(input())
ns = []
for _ in range(T):
	ns.append(int(input()))
max_n = max(ns)
table = [[1] * (i + 1) for i in range(max_n + 1)]
for n in range(2, max_n + 1):
	for k in range(1, n):
		table[n][k] = table[n - 1][k - 1] + table[n - 1][k]
for n in ns:
	print(' '.join([str(x % 10 ** 9) for x in table[n]]))


import math
f = math.factorial
T = int(input())
for i in range(T):
	out = ''
	n = int(input())
	k = [z for z in range(n + 1)]
	for j in k:
		out += str(f(n) // (f(j) * f(n - j)) % pow(10, 9)) + ' '
	print(out)


tr = [1]
for i in range(1, 1000):
	nr = (1,) + tuple((tr[i - 1][j] + tr[i - 1][j - 1] for j in range(1, i))) + (1,)
	tr.append(nr)
for _ in range(int(input())):
	print(' '.join(map(lambda x: str(x % 10 ** 9), tr[int(input())])))


t = int(input())
tab = [[1, 1]]
for adsfads in range(t):
	n = int(input())
	for i in range(len(tab), n):
		tab.append([])
		for j in range(i + 2):
			if j == 0 or j == i + 1:
				tab[i].append(1)
			else:
				tab[i].append((tab[i - 1][j - 1] + tab[i - 1][j]) % 10 ** 9)
	for i in range(n + 1):
		print(tab[n - 1][i], end=' ')
	print('')


import math
t = int(input())
for i in range(t):
	n = int(input())
	for k in range(n + 1):
		p = math.factorial(n) // (math.factorial(k) * math.factorial(n - k))
		p = p % 10 ** 9
		print(str(p) + ' ', end='')
	print('\n', end='')


import math

def c(n, m):
	mod = 10 ** 9
	return math.factorial(n) // (math.factorial(m) * math.factorial(n - m)) % mod
t = int(input())
for i in range(t):
	n = int(input())
	print(' '.join((str(c(n, j)) for j in range(0, n + 1))))


import copy
primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]
mod = 1000000000

def multiply(a, b):
	for x in b.keys():
		if x in a:
			a[x] += b[x]
		else:
			a[x] = b[x]
	return

def divide(a, b):
	for x in b.keys():
		a[x] = a[x] - b[x]
	return

def primeFactorisation(a):
	if a <= 1:
		return {}
	ret = {}
	for i in range(len(primes)):
		p = primes[i]
		counter = 0
		while a % p == 0:
			a //= p
			counter += 1
		if counter > 0:
			ret[p] = counter
	return ret

def toInteger(a):
	ret = 1
	for p in a.keys():
		counter = a[p]
		while counter > 0:
			ret = ret * p % mod
			counter -= 1
	return ret
primeFactorisations = [primeFactorisation(x) for x in range(1000)]

def calculateCenter(n):
	k = n // 2
	ret = copy.deepcopy(primeFactorisations[n])
	for x in range(n - k + 1, n):
		multiply(ret, primeFactorisations[x])
	for x in range(2, k + 1):
		divide(ret, primeFactorisations[x])
	return ret

def calculateAllCombinations(n):
	if n == 1:
		print('1 1')
		return
	ret = [0] * (n + 1)
	ret[0] = 1
	ret[n] = 1
	ret[1] = n
	ret[n - 1] = n
	k = n // 2
	current = calculateCenter(n)
	ret[k] = toInteger(current)
	ret[n - k] = ret[k]
	divisor = n - k + 1
	multiplier = k
	for x in range(k - 1, 1, -1):
		divide(current, primeFactorisations[divisor])
		divisor += 1
		multiply(current, primeFactorisations[multiplier])
		multiplier -= 1
		ret[x] = toInteger(current)
		ret[n - x] = ret[x]
	print(' '.join(map(str, ret)))
a = int(input())
b = [int(input()) for i in range(a)]
for x in b:
	calculateAllCombinations(x)


import sys
T = int(sys.stdin.readline())
pascal = [[1], [1, 1]]
for _ in range(T):
	n = int(sys.stdin.readline())
	while n >= len(pascal):
		row = [(pascal[-1][i] + pascal[-1][i + 1]) % 10 ** 9 for i in range(len(pascal) - 1)]
		pascal.append([1] + row + [1])
	print(*pascal[n], sep=' ')


mod = 10 ** 9
nums = []
maxval = 0
for t in range(int(input())):
	nums.append(int(input()))
	if nums[t] > maxval:
		maxval = nums[t]
pascal = [[1, 1]]
for i in range(1, maxval):
	pascal.append([1])
	for j in range(i):
		pascal[i].append((pascal[i - 1][j] + pascal[i - 1][j + 1]) % mod)
	pascal[i].append(1)
for i in nums:
	print(' '.join(map(str, pascal[i - 1])))


T = int(input(''))
d = dict()
for i in range(T):
	n = int(input(''))
	d[0] = 1
	for r in range(1, n // 2 + 1):
		d[r] = d[r - 1] * (n - r + 1) // r
	for r in range(0, n // 2 + 1):
		print(d[r] % 10 ** 9, end=' ')
	for r in range(n // 2 + 1, n + 1):
		print(d[n - r] % 10 ** 9, end=' ')
	print('')


import math
t = int(input())
while t > 0:
	values = []
	t -= 1
	n = int(input())
	lenth = math.ceil((n + 1) / 2)
	Nfact = math.factorial(n)
	for r in range(0, lenth):
		Rfact = math.factorial(r)
		R_Nfact = math.factorial(n - r)
		val = Nfact // (Rfact * R_Nfact)
		values.append(val % 1000000000)
	for i in values:
		print(i, end=' ')
	if n % 2 == 0:
		for i in range(2, len(values) + 1):
			print(values[-i], end=' ')
	else:
		for i in range(1, len(values) + 1):
			print(values[-i], end=' ')
	print()


def table(n):
	c = 1
	print(1, end=' ')
	ans = [1]
	for r in range(1, n // 2 + 1):
		c = c * (n - r + 1) // r
		ans.append(c % 1000000000)
		print(ans[-1], end=' ')
	if not n % 2:
		ans.pop()
	while ans:
		print(ans.pop() % 1000000000, end=' ')
t = int(input())
ip = list()
for i in range(t):
	ip.append(int(input()))
for n in ip:
	table(n)
	print('')


fact = {}
DIV = 1000000000

def find_fact(n):
	if n == 0 or n == 1:
		fact[n] = 1
	elif n not in fact:
		fact[n] = find_fact(n - 1) * n
	return fact[n]

def find_nCr(n, r):
	numr = find_fact(n)
	dumr = find_fact(n - r) * find_fact(r)
	result = numr // dumr % DIV
	return result
t = int(input())
for _ in range(t):
	n = int(input())
	for r in range(n + 1):
		print(find_nCr(n, r), end=' ')
	print()


C = [[1 for _ in range(1001)] for _ in range(1001)]
for i in range(1001):
	for j in range(1, i):
		C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % 1000000000
for _ in range(int(input())):
	print(*(lambda n: C[n][:n + 1])(int(input())))


def create_generator():
	prev = [1, 1]
	while True:
		res = [prev[0]]
		for i in range(1, len(prev)):
			res.append((prev[i - 1] + prev[i]) % 1000000000)
		res.append(prev[len(prev) - 1])
		prev = res
		yield res

def cnk(n, memo, gen):
	for i in range(len(memo), n + 1):
		memo.append(next(gen))
	return memo[n]
known = [[1], [1, 1]]
generator = create_generator()
for _ in range(int(input().strip())):
	print(' '.join(map(str, cnk(int(input().strip()), known, generator))))


t = int(input())
for _ in range(t):
	n = int(input())
	ar = [0] * (n + 1)
	ar[0] = 1
	for k in range(1, n + 1):
		ar[k] = ar[k - 1] * (n - k + 1) // k
	print(' '.join([str(x % 10 ** 9) for x in ar]))


num_of_input = int(input())
inputs = []
for i in range(num_of_input):
	a = int(input())
	inputs.append(a)
import math

def C(n, r):
	numerator = 1
	denominator = 1
	while r > 0:
		numerator = numerator * n
		denominator = denominator * r
		n = n - 1
		r = r - 1
	return numerator // denominator

def total_combo(n):
	L = []
	k = math.ceil(n / 2)
	for i in range(k):
		L.append(C(n, i) % 10 ** 9)
	M = L[:]
	M.reverse()
	if n % 2 == 0:
		L.append(C(n, k) % 10 ** 9)
	L.extend(M)
	return stringify(L)

def stringify(L):
	s = ''
	for i in L:
		s = s + str(i) + ' '
	return s[:-1]
for i in inputs:
	print(total_combo(i))


MOD = 10 ** 9
T = int(input())
for _ in range(T):
	n = int(input())
	res = [1 for _ in range(n + 1)]
	(m, k) = (1, 1)
	for i in range(1, n + 1):
		m *= n + 1 - i
		k *= i
		res[i] = m // k % MOD
	print(*res)


from math import factorial
for i in range(0, int(input())):
	n = int(input()) + 1
	row = [1]
	k = [0]
	pascTri = []
	for x in range(max(n, 0)):
		pascTri.append(row)
		row = [l + r for (l, r) in zip(row + k, k + row)]
	for j in pascTri[-1]:
		print(j % pow(10, 9), end=' ')
	print()


matr = [[0 for i in range(1001)] for j in range(1001)]
for i in range(0, 1001):
	matr[0][i] = matr[i][i] = 1
for i in range(2, 1001):
	for j in range(1, i):
		matr[i][j] = (matr[i - 1][j - 1] + matr[i - 1][j]) % 1000000000
t = int(input())
for k in range(0, t):
	x = int(input())
	for p in range(1, x + 2):
		print(matr[x + 1][p], end=' ')
	print('')


rows = [[1]]
rowsSoFar = 0
numTests = int(input())
for test in range(numTests):
	rowToPrint = int(input())
	while rowsSoFar < rowToPrint:
		newRow = [1]
		for ix in range(len(rows[-1]) - 1):
			newRow.append((rows[-1][ix] + rows[-1][ix + 1]) % 10 ** 9)
		newRow.append(1)
		rows.append(newRow)
		rowsSoFar += 1
	print(' '.join((str(n) for n in rows[rowToPrint])))


def generateFact(num):
	factorials = []
	factorials.append(1)
	factorials.append(1)
	i = 2
	while i <= num:
		factorials.append(i * factorials[i - 1])
		i += 1
	return factorials

def getnCr(num, factorials):
	i = 0
	numFact = factorials[num]
	while i <= num:
		resi = factorials[i] * factorials[num - i]
		print(numFact // resi % 1000000000, end=' ')
		i += 1
testCase = int(input())
factorials = generateFact(1000)
while testCase > 0:
	n = int(input())
	getnCr(n, factorials)
	print()
	testCase -= 1


def ncr(n, r):
	r = min(r, n - r)
	if r == 0:
		return 1
	numer = 1
	denom = 1
	for i in range(n, n - r, -1):
		numer *= i
	for i in range(1, r + 1):
		denom *= i
	return numer // denom % 10 ** 9
t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	for i in range(n + 1):
		print(ncr(n, i), end=' ')
	print()


import math
mod = 10 ** 9

def C(n, r):
	return math.factorial(n) // math.factorial(r) // math.factorial(n - r)
m = int(input())
while m:
	n = int(input())
	for r in range(n + 1):
		print(C(n, r) % mod, end=' ')
	print()
	m = m - 1


mod = 10 ** 9
for _ in range(int(input())):
	n = int(input())
	curr = 0
	for i in range(n + 1):
		if i == 0:
			curr = 1
		else:
			curr = curr * (n - i + 1) // i
		print(curr % mod, end=' ')
	print()


ncr = [[0] * (n + 1) for n in range(1001)]
for n in range(1001):
	ncr[n][0] = ncr[n][n] = 1
	for r in range(1, n):
		ncr[n][r] = (ncr[n - 1][r] + ncr[n - 1][r - 1]) % 1000000000
T = int(input())
for _ in range(T):
	n = int(input())
	print(' '.join(map(str, ncr[n])))


def printar(a):
	x = ' '.join(map(str, a))
	print(x)

def modit(a):
	b = []
	for i in a:
		b.append(i % 1000000000)
	return b
t = int(input().strip())
max = 1
pas = [[], [1, 1]]
for tt in range(t):
	n = int(input().strip())
	if n > max:
		for i in range(max, n + 1):
			nr = []
			old = 0
			for j in pas[max]:
				jj = old + j
				nr.append(jj)
				old = j
			nr.append(1)
			pas.append(nr)
			max += 1
	printar(modit(pas[n]))


p = 10 ** 9
for _ in range(int(input())):
	n = int(input())
	cs = [1, n]
	for i in range(2, n + 1):
		cs.append(cs[i - 1] * (n - i + 1) // i)
	print(' '.join([str(i % p) for i in cs]))


import math

def binomial(n, r):
	return math.factorial(n) // math.factorial(n - r) // math.factorial(r) % 10 ** 9

def binomials(n):
	return [binomial(n, i) for i in range(n + 1)]
for _ in range(int(input())):
	n = int(input())
	print(' '.join(map(str, binomials(n))))


pascal = []
pascal.append([1])
for i in range(1, 1002):
	line = [None] * (i + 1)
	for j in range(0, i):
		if j == 0:
			line[0] = line[i] = 1
		elif j == 1:
			line[1] = line[i - 1] = i
		else:
			line[j] = (pascal[i - 1][j - 1] + pascal[i - 1][j]) % 1000000000
	pascal.append(line)
t = int(input())
for ii in range(0, t):
	n = int(input())
	[print(pascal[n][i], end=' ') for i in range(n + 1)]
	print()


P = []

def choose(n, k):
	if n == k or k == 0:
		return 1
	if P[n][k] != -1:
		return P[n][k]
	res = (choose(n - 1, k - 1) + choose(n - 1, k)) % 10 ** 9
	P[n][k] = res
	return res
P = [[-1 for y in range(1001)] for x in range(1001)]
t = int(input())
for z in range(t):
	n = int(input())
	res = []
	for i in range(n + 1):
		res.append(choose(n, i))
	print(' '.join(map(str, res)))


import sys
T = int(sys.stdin.readline())
pascal = [[1], [1, 1]]
for _ in range(T):
	n = int(sys.stdin.readline())
	while n >= len(pascal):
		row = [(pascal[-1][i] + pascal[-1][i + 1]) % 10 ** 9 for i in range(len(pascal) - 1)]
		pascal.append([1] + row + [1])
	print(*pascal[n], sep=' ')


from itertools import repeat

def ncr(n):
	c = [list(repeat(0, i + 1)) for i in range(n + 1)]
	for i in range(n + 1):
		(c[i][0], c[i][i]) = (1, 1)
	for i in range(2, n + 1):
		for j in range(1, i):
			c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % 1000000000
	return c
a = []
for t in range(int(input())):
	a.append(int(input()))
nmax = max(a)
c = ncr(nmax)
for x in a:
	print(' '.join(map(str, c[x])))


def pascal(n):
	x = [[1] * (i + 1) for i in range(n + 1)]
	for r in range(2, n + 1):
		for c in range(1, r):
			x[r][c] = (x[r - 1][c - 1] + x[r - 1][c]) % 1000000000
	return x
t = int(input())
cases = []
xmax = 0
for j in range(t):
	x = int(input())
	if x > xmax:
		xmax = x
	cases.append(x)
c = pascal(xmax)
for i in cases:
	print(' '.join(map(str, c[i])))


d = {(0, 0): 1}

def nCr(n, r):
	if r == 0 or r == n:
		d[n, r] = 1
		return 1
	if (n, r) in d.keys():
		return d[n, r]
	d[n, r] = nCr(n - 1, r) + nCr(n - 1, r - 1)
	return d[n, r]
t = int(input())
for i in range(t):
	n = int(input())
	l = []
	for j in range(n + 1):
		l.append(nCr(n, j) % 1000000000)
	print(' '.join(map(str, l)))


def pascal_triangle(n, mod):
	pascal = [x[:] for x in [[0] * (n + 1)] * (n + 1)]
	pascal[0][0] = 1
	for i in range(1, n + 1):
		pascal[i][0] = 1
		for j in range(1, i + 1):
			pascal[i][j] = (pascal[i - 1][j] + pascal[i - 1][j - 1]) % mod
	return pascal
pascal = pascal_triangle(1000, pow(10, 9))
for t in range(int(input().strip())):
	n = int(input().strip())
	for i in range(n + 1):
		print(pascal[n][i], end=' ')
	print()


def total_ls(k):
	res = [1]
	for i in range(k // 2):
		res.append(res[-1] * (k - i) // (i + 1))
	leghth = len(res)
	if k % 2 == 0:
		leghth -= 1
	res.extend(res[:leghth][::-1])
	return res
MOD_NUMBER = 10 ** 9
n = int(input())
for _ in range(n):
	k = int(input())
	res = total_ls(k)
	for i in res:
		print(i % MOD_NUMBER, end=' ')
	print('')


__author__ = 'Shivani'
import math

def ncr(n):
	l = [1]
	m = 10 ** 9
	f = 1
	for i in range(1, n // 2 + 1):
		f = f * (n + 1 - i) // i
		l.append(f)
	if n & 1:
		l.extend(list(reversed(l)))
	else:
		l.extend(list(reversed(l[:-1])))
	s = ''
	for i in l:
		s += str(i % m) + ' '
	print(s)

def main():
	for i in range(int(input())):
		ncr(int(input()))
main()


def NCRtable(n):
	a = [[1], [1, 1]]
	for row in range(2, n):
		r = [1]
		for entry in range(1, row):
			r.append(a[row - 1][entry] + a[row - 1][entry - 1])
		r.append(1)
		a.append(r)
	return a
q = []
for i in range(int(input())):
	q.append(int(input()))
m = max(q)
NCR = NCRtable(m + 1)
for i in q:
	print(' '.join([str(j % 10 ** 9) for j in NCR[i]]))


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	temp = 1
	print(1, end=' ')
	for i in range(1, n + 1):
		temp = temp * (n - i + 1) // i
		print(temp % 10 ** 9, end=' ')
	print('')


T = int(input())
K = 10 ** 9
for t in range(T):
	n = int(input())
	c = 1
	for k in range(n + 1):
		print(c % K, end=' ')
		c *= n - k
		c //= k + 1
	print()


def fakulteta(n):
	if n == 0 or n == 1:
		return 1
	vrni = 1
	while n > 1:
		vrni *= n
		n = n - 1
	return vrni

def funkcija(n):
	zgornji = fakulteta(n)
	seznam = []
	for i in range(n // 2 + 1):
		dodaj = zgornji // (fakulteta(i) * fakulteta(n - i))
		seznam.append(dodaj % 10 ** 9)
	vrni = ''
	for x in seznam:
		vrni += str(x) + ' '
	if n % 2 == 0:
		for i in range(2, len(seznam) + 1):
			vrni += str(seznam[-i]) + ' '
	else:
		for i in range(1, len(seznam) + 1):
			vrni += str(seznam[-i]) + ' '
	return vrni
t = input()
t = int(t)
for i in range(t):
	test = input()
	test = int(test)
	print(funkcija(test))


from math import factorial
size = int(input())
for i in range(size):
	n = int(input())
	top = factorial(n)
	for r in range(n + 1):
		ans = top // factorial(n - r)
		ans = ans // factorial(r)
		ans %= 10 ** 9
		print('%d' % ans, end=' ')
	print('')


table = [0] * 1000
for row in range(1000):
	table[row] = []
	for col in range(row + 1):
		table[row].append(1 if col == 0 or col == row else (table[row - 1][col - 1] + table[row - 1][col]) % 1000000000)
for _ in range(int(input())):
	print(' '.join(map(str, table[int(input())])))


mod = 10 ** 9

def scan(op, seq, it):
	a = []
	result = it
	a.append(it)
	for x in seq:
		result = op(result, x)
		a.append(result)
	return a

def pascal(n):

	def nextrow(row, x):
		return [l + r for (l, r) in zip(row + [0], [0] + row)]
	return scan(nextrow, range(n - 1), [1])
P = pascal(1001)
T = int(input())
for _ in range(T):
	print(' '.join((str(x % mod) for x in P[int(input())])))


from math import factorial
m = 10 ** 9
for _ in range(int(input())):
	n = int(input())
	h = n // 2
	s1 = [str(factorial(n) // (factorial(i) * factorial(n - i)) % m) for i in range(h + 1)]
	s2 = list(reversed(s1[:h + n % 2]))
	print(' '.join(s1 + s2))


MOD = 1000000000
cache = {1: (1, 1)}

def get_row(n):
	if n in cache:
		return cache[n]
	prev = (0,) + get_row(n - 1) + (0,)
	result = tuple(((prev[i] + prev[i + 1]) % MOD for i in range(n + 1)))
	cache[n] = result
	return result
for t in range(int(input())):
	print(' '.join(map(str, get_row(int(input())))))


def ncr(n, r, ncrs):
	if ncrs[n][r] != -1:
		return ncrs[n][r] % 1000000000
	if n == r:
		ncrs[n][r] = 1
		return 1
	if r == 0:
		ncrs[n][r] = 1
		return 1
	if r == 1:
		ncrs[n][r] = n
		return n
	ncrs[n][r] = ncr(n - 1, r, ncrs) + ncr(n - 1, r - 1, ncrs)
	return ncrs[n][r] % 1000000000
t = int(input())
ncrs = [[-1 for x in range(1000)] for y in range(1000)]
for i in range(t):
	curr = int(input())
	print(' '.join([str(ncr(curr, i, ncrs)) for i in range(curr + 1)]))


modulo = 10 ** 9
comb_dict = {}

def Comb(n, tmp):
	r = tmp
	if n - tmp < r:
		r = n - tmp
	if r == 0:
		return 1
	nr = (n, r)
	if nr in comb_dict:
		return comb_dict[n, r]
	comb_dict[nr] = (Comb(n - 1, r) + Comb(n - 1, r - 1)) % modulo
	return comb_dict[nr]
T = int(input())
for tmp in range(T):
	N = int(input())
	for cnt in range(N + 1):
		print(Comb(N, cnt), end=' ')
	print()


N = int(input())
L = []
for i in range(N):
	L.append(int(input()))
T = [[1], [1, 1]]
for i in range(2, max(L) + 1):
	temp = [1]
	for j in range(i - 1):
		t = T[i - 1][j] + T[i - 1][j + 1]
		t %= 10 ** 9
		temp.append(t)
	temp.append(1)
	T.append(temp)
for i in L:
	for j in T[i]:
		print(j, end=' ')
	print()


a = [[1], [1, 1], [1, 2, 1]]
for i in range(3, 1000):
	x = []
	x.append(1)
	for j in range(i - 1):
		x.append((a[i - 1][j] + a[i - 1][j + 1]) % 10 ** 9)
	x.append(1)
	a.append(x)
for _ in range(int(input())):
	N = int(input())
	ans = a[N]
	for i in ans:
		print(i, end=' ')
	print()


T = int(input())
for _ in range(T):
	n = int(input())
	n_k = [1]
	for k in range(0, n):
		n_k.append(n_k[k] * (n - k) // (k + 1))
	print(' '.join([str(int(i % 10 ** 9)) for i in n_k]))


triangle = [[1], [1, 1]]
for i in range(1, 1000):
	triangle.append([1] + [(triangle[i][j] + triangle[i][j + 1]) % 10 ** 9 for j in range(i)] + [1])
triangle = [' '.join([str(i) for i in row]) for row in triangle]
n = int(input())
for i in range(n):
	k = int(input())
	print(triangle[k])


def nCk(n, k):
	nk = min(k, n - k)
	b = 1
	for _i in range(nk):
		b *= n - _i
		b //= _i + 1
	return b
mod = 10 ** 9
t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	print(*(nCk(n, i) % mod for i in range(n + 1)))


t = int(input())
f = [[], [1, 1]]
for i in range(2, 1001):
	for j in range(i + 1):
		if j == 0:
			f.append([1])
		elif j > (i + 1) // 2:
			f[i].append(f[i][i - j])
		else:
			f[i].append((f[i - 1][j - 1] + f[i - 1][j]) % pow(10, 9))
for i in range(t):
	n = int(input())
	for j in range(n + 1):
		print(f[n][j], end=' ')
	print()


import sys
f = sys.stdin
T = int(f.readline())
N = 1001
preval = [[1], [1, 1]]
for i in range(2, N):
	new = [1, i]
	for col in range(2, i):
		new += [int((preval[i - 1][col] + preval[i - 1][col - 1]) % 1000000000.0)]
	new += [1]
	preval.append(new)
for i in range(T):
	n = int(f.readline())
	print(' '.join((str(preval[n][i]) for i in range(len(preval[n])))))


t = input()
v = []
ncr_t = {}

def ncr(n, r):
	if n == r or r == 0:
		ncr_t[n, r] = 1
		return 1
	if r == 1:
		ncr_t[n, r] = n
		return n
	try:
		return ncr_t[n, r]
	except:
		ncr_t[n, r] = (ncr(n - 1, r - 1) + ncr(n - 1, r)) % 1000000000
		return ncr_t[n, r]
for i in range(0, int(t)):
	v = int(input())
	for i in range(0, v + 1):
		ncr_t[v, i] = ncr(v, i)
		print(ncr_t[v, i], end=' ')
	print('')


T = int(input())
for i in range(T):
	L = [1]
	N = int(input()) + 1
	for j in range(1, N):
		p = L[-1]
		L.append(p * (N - j) // j)
	[print(v % 10 ** 9, end=' ') for v in L]
	print()


from math import factorial
for _ in range(int(input())):
	n = int(input())
	arr = []
	for r in range(n + 1):
		arr.append(factorial(n) // (factorial(r) * factorial(n - r)) % 10 ** 9)
	print(' '.join(map(str, arr)))


MAXN = 1005
MOD = 1000000000
nCr = [[0 for x in range(MAXN)] for i in range(MAXN)]

def Preprocess():
	nCr[0][0] = 0
	nCr[1][0] = 1
	nCr[1][1] = 1
	for i in range(2, MAXN):
		nCr[i][0] = 1
		for j in range(1, i + 1):
			nCr[i][j] = nCr[i - 1][j - 1] + nCr[i - 1][j]
			if nCr[i][j] >= MOD:
				nCr[i][j] %= MOD

def solve():
	N = int(input())
	ans = ''
	for i in range(0, N + 1):
		ans += str(nCr[N][i]) + ' '
	print(ans)

def main():
	Preprocess()
	t = int(input())
	while t > 0:
		solve()
		t -= 1
main()


def pascal(n, k, m1):
	if k == 0 or k == n:
		return 1
	elif (n, k) in cache:
		return cache[n, k]
	else:
		value = (pascal(n - 1, k - 1, m1) + pascal(n - 1, k, m1)) % m1
		cache[n, k] = value
		return value
cache = {}
m1 = 1000000000
nTst = int(input())
for t1 in range(nTst):
	nn = int(input())
	for r1 in range(nn + 1):
		print(pascal(nn, r1, m1), ' ', sep='', end='')
	print()


MOD = 10 ** 9

def f(e):
	return str(e % MOD)

def solve(n):
	lis = [1]
	for ctr in range(1, n // 2 + 1):
		lis.append(lis[-1] * (n - ctr + 1) // ctr)
	if n & 1 == 0:
		lis += reversed(lis[0:len(lis) - 1])
	else:
		lis += reversed(lis)
	return map(f, lis)

def main():
	cases = int(input())
	for c in range(cases):
		n = int(input())
		print(' '.join(solve(n)))
main()


n = int(input().strip())
b = [[1, 1]]
c = []
s = ' '
for num in range(n):
	z = int(input().strip())
	z -= 1
	if z <= len(b) - 1:
		for j in range(len(b[z])):
			c.append(str(b[z][j] % 1000000000))
		print(s.join(c))
		c = []
		continue
	for k in range(z + 1 - len(b)):
		b.append([1])
		for num in range(len(b[-2]) - 1):
			b[-1].append(b[-2][num] + b[-2][num + 1])
		b[-1].append(1)
	for j in range(len(b[-1])):
		c.append(str(b[-1][j] % 1000000000))
	print(s.join(c))
	c = []


nCr = [[1]]
for i in range(1, 1000):
	nCr += [[1] + [(nCr[i - 1][j] + nCr[i - 1][j + 1]) % 10 ** 9 for j in range(i - 1)] + [1]]
t = int(input())
for _ in range(t):
	print(*nCr[int(input())])


import math as m
f = m.factorial

def nCr(n, r):
	return f(n) // (f(n - r) * f(r))

def do_thing(n):
	return ' '.join([str(nCr(n, i) % 10 ** 9) for i in range(n + 1)])
T = int(input().strip())
for i in range(T):
	print(do_thing(int(input().strip())))


K = 10 ** 9
f = [[1 for i in range(1000)] for j in range(1000)]
for i in range(2, 1000):
	for j in range(1, i):
		f[i][j] = (f[i - 1][j - 1] + f[i - 1][j]) % K
for _ in range(int(input())):
	n = int(input())
	print(1, sep='', end='')
	for i in range(1, n + 1):
		print('', f[n][i], end='')
	print()


T = int(input())
n = []
for i in range(T):
	n.append(int(input()))
pascal = []
pascal.append([1])
pascal.append([1, 1])
pascal.append([1, 2, 1])

def nCr(n, k):
	if n < len(pascal):
		return pascal[n][k]
	else:
		generaterow(k)
		return pascal[n][k]

def generaterow(k):
	if k > len(pascal):
		generaterow(k - 1)
	pascal.append([])
	for i in range(k + 1):
		if i == 0:
			pascal[k].append(1)
		elif i == k:
			pascal[k].append(1)
		else:
			pascal[k].append(pascal[k - 1][i - 1] + pascal[k - 1][i])

def printrow(n):
	for i in range(n):
		print(pascal[n][i] % 1000000000, end=' ')
	print(1)
generaterow(max(n))
for val in n:
	printrow(val)


ncr = [[1]]
for i in range(1000):
	cur = ncr[-1]
	nex = cur + [0]
	for i in range(0, len(cur)):
		nex[i + 1] = (nex[i + 1] + cur[i]) % 1000000000
	ncr.append(nex)
for xx in range(int(input())):
	print(' '.join(map(str, ncr[int(input())])))


def vrsta(n):
	sez = [1]
	a = n
	for k in range(1, n):
		a //= k
		sez.append(a % 10 ** 9)
		a *= n - k
	sez.append(1)
	return sez
for _ in range(int(input())):
	print(' '.join((str(x) for x in vrsta(int(input())))))


import math

def newt(n, k):
	x = math.factorial(n) // (math.factorial(k) * math.factorial(n - k))
	return x % 10 ** 9
for _ in range(int(input())):
	k = int(input())
	print(' '.join((str(newt(k, i)) for i in range(k + 1))))


import math

def prep(N):
	l = [[0], [1], [1, 2, 1]]
	for nm in range(N):
		pr = 0
		l += [[]]
		for v in l[-2]:
			l[-1] += [(pr + v) % 10 ** 9]
			pr = v
		l[-1] += [1]
	return l

def genfas(N):
	nf = int(math.sqrt(N))
	fal = [dict(), dict()]
	for n in range(2, N):
		re = dict()
		for d in [2] + list(range(3, nf + 1, 2)):
			p = 0
			(q, r) = divmod(n, d)
			while r == 0:
				p += 1
				n = q
				(q, r) = divmod(n, d)
			if p:
				re[d] = p
		if n != 1:
			re[n] = 1
		fal += [re]
	return fal

def addsubfas(facs, fas, add=True):
	if trace & 1:
		print('\t' + 'add' if add else 'sub', facs, fas)
	for it in fas.keys():
		facs[it] = facs.get(it, 0) + (fas[it] if add else -fas[it])
		if facs[it] == 0:
			del facs[it]
	if trace & 1:
		print('\t' + ('add' if add else 'sub') + 'ed res:', facs)

def val(facs, modo=10 ** 9):
	r = 1
	for it in facs.items():
		r = r * pow(it[0], it[1], modo) % modo
	return r

def cmbs(N):
	r = [1]
	facs = dict()
	for n in range(N):
		if trace & 1:
			print('mul div', N - n, n + 1)
		addsubfas(facs, fal[N - n])
		addsubfas(facs, fal[n + 1], False)
		r += [val(facs)]
	return r
trace = 0
fal = genfas(1000)
l = [[0], [1], [1, 2, 1]]
nc = int(input().strip())
from sys import stdin
for _ in range(nc):
	for v in cmbs(int(input())):
		print(v, end=' ')
	print()


from math import factorial
factorialTable = {}

def fact(x):
	if x in factorialTable:
		return factorialTable[x]
	else:
		return factorial(x)
for _ in range(int(input())):
	n = int(input())
	for i in range(n + 1):
		print(fact(n) // (fact(i) * fact(n - i)) % 1000000000, end=' ')
	print()


t = int(input().strip())
table = [[1]]
for _ in range(1000):
	row = table[-1]
	nxt = [1]
	for i in range(1, len(row)):
		nxt += [(row[i - 1] + row[i]) % 10 ** 9]
	nxt += [1]
	table += [nxt]
for _ in range(t):
	n = int(input().strip())
	print(' '.join([str(c) for c in table[n]]))


memory = [[None for i in range(1000)] for j in range(1000)]

def nCr(n, r):
	if r > n:
		return 0
	if r == n or r == 0:
		return 1
	if r == 1:
		return n
	if n == 0:
		return 1
	if memory[n][r] is not None:
		return memory[n][r]
	v = (nCr(n - 1, r - 1) + nCr(n - 1, r)) % 10 ** 9
	memory[n][r] = v
	return v

def solve(n):
	l = []
	for r in range(n + 1):
		l.append(nCr(n, r))
	print(' '.join((str(x) for x in l)))
T = int(input())
for i in range(T):
	data = map(int, input().split())
	solve(*data)


from math import factorial
T = int(input())
for i in range(T):
	n = int(input())
	for j in range(n + 1):
		print(factorial(n) // (factorial(j) * factorial(n - j)) % 1000000000, end=' ')
	print()


from math import factorial

def nCk(n, r):
	return factorial(n) // factorial(r) // factorial(n - r) % 10 ** 9
for _ in range(int(input())):
	n = int(input())
	print(''.join(('%d ' % nCk(n, k) for k in range(n + 1))))


N = int(input())
Modulus = 10 ** 9
for _ in range(N):
	current = 1
	n = int(input())
	print(1, end=' ')
	for i in range(1, n + 1):
		current = current * (n - i + 1) // i
		print(current % Modulus, end=' ')
	print()