Little Lucy loves to arrange her flowers in patterns similar to those of a binary search tree. Her father, a computer scientist himself, takes note of this and finds out that she has N flowers. Every day she takes some of these N flowers and arranges them into all possible different patterns. The more the number of arrangements, the more time she spends outside.

Now, her father knows that she takes a non-empty subset of these N flowers any given day. He wants to find out the total number of arrangements that she can ever make. As this may be too large to handle, you only need to report final answer modulo 10^{9}+9 if the answer is no less than 10^{9}+9. 

Note: All flowers are distinct and are labelled by distinct numbers.

Input Format 

The first line contains an integer, T, the number of test cases. 

The next T lines contain an integer each, N ,that denotes the number of flowers the girl has.

Output Format 

Output T lines each containing an answer to corresponding query.

Constraints

1 ≤ T ≤ 5000 

1 ≤ N ≤ 5000

Sample Input

4
1
2
3
4

Sample Output

1
4
14
50    

Explanation

For the first case, only one BST is possible. 

For the second case, only 4 BSTs are possible (shown below). 

1    2    1      2
           \    / 
            2   1

Similarly, 14 BSTs are possible for N = 3, and 50 are possible for N = 4.

Source: hackerrank | Difficulty: MEDIUM
Tags: Number theory


Solutions:
import functools
N = 10001
P = 10 ** 9 + 9
fact = [1]
for i in range(1, N):
	fact.append(fact[-1] * i % P)
inv = [0, 1]
for i in range(2, N):
	inv.append(P - P // i * inv[P % i] % P)
inv_fact = [1]
for i in range(1, N):
	inv_fact.append(inv_fact[-1] * inv[i] % P)

def C(n, k):
	return fact[n] * inv_fact[k] % P * inv_fact[n - k] % P

def cat(n):
	return fact[2 * n] * inv_fact[n] % P * inv_fact[n + 1] % P
cat_arr = list(map(cat, range(0, 5001)))

@functools.lru_cache(maxsize=None)
def f(x):
	ret = 0
	for n in range(1, x + 1):
		ret += C(x, n) * cat_arr[n] % P
		ret %= P
	return ret
t = int(input())
for _ in range(t):
	print(f(int(input())))


import sys
cache = {}
sys.setrecursionlimit(5010)

def countBSTs(n):
	if n <= 1:
		return n
	if n in cache:
		return cache[n]
	total = 0
	for i in range(n // 2):
		totalLeft = countBSTs(i)
		totalRight = countBSTs(n - i - 1)
		total += 2 * (totalLeft + totalRight + totalLeft * totalRight + 1)
		total %= 1000000009
	if n % 2 == 1:
		totalLeft = countBSTs(n // 2)
		total += totalLeft * 2 + totalLeft * totalLeft + 1
		total %= 1000000009
	cache[n] = total
	return total
t = int(input())
for testCase in range(t):
	n = int(input())
	print(countBSTs(n) % 1000000009)


def invMod(a, n):
	(t, t_, r, r_) = (0, 1, n, a)
	while r_ != 0:
		q = r // r_
		(t, t_, r, r_) = (t_, t - q * t_, r_, r - q * r_)
	if r > 1:
		return None
	if t < 0:
		t += n
	return t
MOD = 10 ** 9 + 9
Nmax = 5000
Inv = [invMod(i, MOD) for i in range(Nmax + 3)]
(v, C2) = (1, [1])
for i in range(1, Nmax + 1):
	v = v * (2 * i + 1) * (2 * i + 2) * Inv[i + 1] * Inv[i + 2] % MOD
	C2.append(v)
B = {}
T = int(input())
for t in range(T):
	N = int(input())
	if not N in B:
		(b, c) = (0, 1)
		for i in range(N):
			c = c * (N - i) * Inv[i + 1] % MOD
			b += c * C2[i]
		B[N] = b % MOD
	print(B[N])


import sys
MAX_N = 5000
MOD = 1000000009
a = [0, 1]
for n in range(2, MAX_N + 2):
	a.append((1 + sum((a[i] * a[n - i] for i in range(1, n)))) % MOD)
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	print((a[N + 1] - 1) % MOD)


import sys
MAX_N = 5000
MOD = 1000000009
a = [0, 1]
for n in range(2, MAX_N + 2):
	a.append((1 + sum((a[i] * a[n - i] for i in range(1, n)))) % MOD)
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	print((a[N + 1] - 1) % MOD)


import sys
MAX_N = 5000
MOD = 1000000009
a = [0, 1]
for n in range(2, MAX_N + 2):
	a.append((1 + sum((a[i] * a[n - i] for i in range(1, n)))) % MOD)
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	print((a[N + 1] - 1) % MOD)


import sys
MAX_N = 5000
MOD = 1000000009
a = [0, 1]
for n in range(2, MAX_N + 2):
	a.append((1 + sum((a[i] * a[n - i] for i in range(1, n)))) % MOD)
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	print((a[N + 1] - 1) % MOD)


M = 10 ** 9 + 9
P = [-1 for _ in range(5005)]
t = int(input())
P[0] = 0
P[1] = 1
last = 1
for _ in range(t):
	n = int(input())
	if n < last:
		print(P[n])
	else:
		for x in range(last + 1, n + 1):
			res = 0
			for i in range(1, x + 1):
				res = ((P[i - 1] + 1) * (P[x - i] + 1) % M + res) % M
			P[x] = res
		last = n
		print(P[n])


p = 1000000009
max_n = 5001
max_fact = 2 * max_n - 1
factorial = [1] * max_fact
inv_factorial = [1] * max_fact
catalan = [1] * max_n
answer = [1] * max_n

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	(g, y, x) = egcd(b % a, a)
	return (g, x - b // a * y, y)

def mod_inv(a, m):
	(gcd, x, y) = egcd(a, m)
	if gcd != 1:
		return None
	return x % m

def nCr(n, r):
	return factorial[n] * inv_factorial[r] * inv_factorial[n - r] % p
for n in range(1, max_fact):
	factorial[n] = n * factorial[n - 1] % p
	inv_factorial[n] = mod_inv(n, p) * inv_factorial[n - 1] % p
for n in range(max_n):
	catalan[n] = factorial[2 * n] * inv_factorial[n + 1] * inv_factorial[n] % p
	answer[n] = (sum((nCr(n, k) * catalan[k] for k in range(n + 1))) - 1) % p
for _ in range(int(input())):
	print(answer[int(input())])


MAX_N = 5000
MOD = 1000000009
a = [0, 1]
for n in range(2, MAX_N + 2):
	a.append((1 + sum((a[i] * a[n - i] for i in range(1, n)))) % MOD)
T = int(input())
ans = []
for _ in range(T):
	N = int(input())
	ans.append((a[N + 1] - 1) % MOD)
for i in range(T):
	print(ans[i])


mod = 10 ** 9 + 9
T = int(input())
N = []
for t in range(T):
	n = int(input())
	N.append(n)
lim = max(N) + 1
f = [0] * lim
for n in range(lim):
	s = 1
	if n & 1:
		s = (s + f[n // 2] ** 2) % mod
	for i in range(n // 2):
		s = (s + 2 * f[i] * f[n - 1 - i]) % mod
	f[n] = s
for n in N:
	print(f[n] - 1)


p = 10 ** 9 + 9
thresh = 5000
a = [0, 1]
for n in range(2, thresh + 1):
	a.append(((6 * n - 2) * a[n - 1] - (5 * n - 5) * a[n - 2] + 2) * pow(n + 1, p - 2, p) % p)
T = int(input())
for t in range(T):
	N = int(input())
	print(a[N])


mod = 10 ** 9 + 9

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('modular inverse does not exist')
	else:
		return x % m

def comb(n, r):
	if r > n - r:
		r = n - r
	num = 1
	den = 1
	for i in range(r):
		num *= n - i
		num %= mod
		den *= i + 1
		den %= mod
	return num * modinv(den, mod) % mod
term = 1
terms = [1]
for r in range(1, 5001):
	term *= 2 * r * (2 * r - 1)
	term %= mod
	term *= modinv(r * r * (r + 1), mod)
	term %= mod
	terms.append(term)

def memoized(func):
	cache = {}

	def newfunc(*args):
		if args not in cache:
			cache[args] = func(*args)
		return cache[args]
	return newfunc

@memoized
def func(n):
	res = 0
	term = 1
	fac = 1
	for r in range(1, n + 1):
		fac = fac * (n - r + 1) % mod
		res += terms[r] * fac % mod
		res %= mod
	return res
for i in range(int(input())):
	n = int(input())
	print(func(n))


import sys
MAX_N = 5000
MOD = int(1000000000.0 + 9)

def main():
	ways = [1] * (MAX_N + 1)
	for i in range(1, MAX_N + 1):
		for j in range(i):
			ways[i] += ways[j] * ways[i - 1 - j]
			ways[i] %= MOD
	t = int(input())
	for _ in range(t):
		n = int(input())
		print(ways[n] - 1)
sys.exit(main())


import sys
MAX_N = 5000
MOD = int(1000000000.0 + 9)

def main():
	ways = [1] * (MAX_N + 1)
	for i in range(1, MAX_N + 1):
		for j in range(i):
			ways[i] += ways[j] * ways[i - 1 - j]
			ways[i] %= MOD
	t = int(input())
	for _ in range(t):
		n = int(input())
		print(ways[n] - 1)
sys.exit(main())


import math
import os
import random
import re
import sys
MAX_N = 5000
MOD = int(1000000000.0 + 9)

def solve():
	ways = [1] * (MAX_N + 1)
	for i in range(1, MAX_N + 1):
		for j in range(i):
			ways[i] += ways[j] * ways[i - 1 - j]
			ways[i] %= MOD
	t = int(input())
	for _ in range(t):
		n = int(input())
		print(ways[n] - 1)
sys.exit(solve())


import sys
MAX_N = 5000
MOD = int(1000000000.0 + 9)

def main():
	ways = [1] * (MAX_N + 1)
	for i in range(1, MAX_N + 1):
		for j in range(i):
			ways[i] += ways[j] * ways[i - 1 - j]
			ways[i] %= MOD
	t = int(input())
	for _ in range(t):
		n = int(input())
		print(ways[n] - 1)
sys.exit(main())


import sys
MAX_N = 5000
MOD = int(1000000000.0 + 9)

def main():
	ways = [1] * (MAX_N + 1)
	for i in range(1, MAX_N + 1):
		for j in range(i):
			ways[i] += ways[j] * ways[i - 1 - j]
			ways[i] %= MOD
	t = int(input())
	for _ in range(t):
		n = int(input())
		print(ways[n] - 1)
sys.exit(main())


import math
import os
import random
import sys
MAX_N = 5000
MOD = int(1000000000.0 + 9)

def main():
	ways = [1] * (MAX_N + 1)
	for i in range(1, MAX_N + 1):
		for j in range(i):
			ways[i] += ways[j] * ways[i - 1 - j]
			ways[i] %= MOD
	t = int(input())
	for _ in range(t):
		n = int(input())
		print(ways[n] - 1)
sys.exit(main())


import sys
MAX_N = 5000
MOD = int(1000000000.0 + 9)

def main():
	ways = [1] * (MAX_N + 1)
	for i in range(1, MAX_N + 1):
		for j in range(i):
			ways[i] += ways[j] * ways[i - 1 - j]
			ways[i] %= MOD
	t = int(input())
	for _ in range(t):
		n = int(input())
		print(ways[n] - 1)
sys.exit(main())


import sys
MAX_N = 5000
MOD = int(1000000000.0 + 9)

def main():
	ways = [1] * (MAX_N + 1)
	for i in range(1, MAX_N + 1):
		for j in range(i):
			ways[i] += ways[j] * ways[i - 1 - j]
			ways[i] %= MOD
	t = int(input())
	for _ in range(t):
		n = int(input())
		print(ways[n] - 1)
sys.exit(main())


import sys
MAX_N = 5000
MOD = int(1000000000.0 + 9)

def main():
	ways = [1] * (MAX_N + 1)
	for i in range(1, MAX_N + 1):
		for j in range(i):
			ways[i] += ways[j] * ways[i - 1 - j]
			ways[i] %= MOD
	t = int(input())
	for _ in range(t):
		n = int(input())
		print(ways[n] - 1)
sys.exit(main())


import sys
MAX_N = 5000
MOD = int(1000000000.0 + 9)

def main():
	ways = [1] * (MAX_N + 1)
	for i in range(1, MAX_N + 1):
		for j in range(i):
			ways[i] += ways[j] * ways[i - 1 - j]
			ways[i] %= MOD
	t = int(input())
	for _ in range(t):
		n = int(input())
		print(ways[n] - 1)
sys.exit(main())


import sys
MAX_N = 5000
MOD = int(1000000000.0 + 9)

def main():
	ways = [1] * (MAX_N + 1)
	for i in range(1, MAX_N + 1):
		for j in range(i):
			ways[i] += ways[j] * ways[i - 1 - j]
			ways[i] %= MOD
	t = int(input())
	for _ in range(t):
		n = int(input())
		print(ways[n] - 1)
sys.exit(main())


import sys
MAX_N = 5000
MOD = int(1000000000.0 + 9)

def main():
	ways = [1] * (MAX_N + 1)
	for i in range(1, MAX_N + 1):
		for j in range(i):
			ways[i] += ways[j] * ways[i - 1 - j]
			ways[i] %= MOD
	t = int(input())
	for _ in range(t):
		n = int(input())
		print(ways[n] - 1)
sys.exit(main())


import sys
MAX_N = 5000
MOD = int(1000000000.0 + 9)

def main():
	ways = [1] * (MAX_N + 1)
	for i in range(1, MAX_N + 1):
		for j in range(i):
			ways[i] += ways[j] * ways[i - 1 - j]
			ways[i] %= MOD
	t = int(input())
	for _ in range(t):
		n = int(input())
		print(ways[n] - 1)
sys.exit(main())


import sys
MAX_N = 5000
MOD = int(1000000000.0 + 9)

def main():
	ways = [1] * (MAX_N + 1)
	for i in range(1, MAX_N + 1):
		for j in range(i):
			ways[i] += ways[j] * ways[i - 1 - j]
			ways[i] %= MOD
	t = int(input())
	for _ in range(t):
		n = int(input())
		print(ways[n] - 1)
sys.exit(main())


import sys
MAX_N = 5000
MOD = int(1000000000.0 + 9)

def main():
	ways = [1] * (MAX_N + 1)
	for i in range(1, MAX_N + 1):
		for j in range(i):
			ways[i] += ways[j] * ways[i - 1 - j]
			ways[i] %= MOD
	t = int(input())
	for _ in range(t):
		n = int(input())
		print(ways[n] - 1)
sys.exit(main())


import sys
MAX_N = 5000
MOD = int(1000000000.0 + 9)

def main():
	ways = [1] * (MAX_N + 1)
	for i in range(1, MAX_N + 1):
		for j in range(i):
			ways[i] += ways[j] * ways[i - 1 - j]
			ways[i] %= MOD
	t = int(input())
	for _ in range(t):
		n = int(input())
		print(ways[n] - 1)
sys.exit(main())


import sys
MAX_N = 5000
MOD = int(1000000000.0 + 9)

def main():
	ways = [1] * (MAX_N + 1)
	for i in range(1, MAX_N + 1):
		for j in range(i):
			ways[i] += ways[j] * ways[i - 1 - j]
			ways[i] %= MOD
	t = int(input())
	for _ in range(t):
		n = int(input())
		print(ways[n] - 1)
sys.exit(main())


import sys
MAX_N = 5000
MOD = int(1000000000.0 + 9)

def main():
	ways = [1] * (MAX_N + 1)
	for i in range(1, MAX_N + 1):
		for j in range(i):
			ways[i] += ways[j] * ways[i - 1 - j]
			ways[i] %= MOD
	t = int(input())
	for _ in range(t):
		n = int(input())
		print(ways[n] - 1)
sys.exit(main())


import functools
N = 10001
P = 10 ** 9 + 9
fact = [1]
for i in range(1, N):
	fact.append(fact[-1] * i % P)
inv = [0, 1]
for i in range(2, N):
	inv.append(P - P // i * inv[P % i] % P)
inv_fact = [1]
for i in range(1, N):
	inv_fact.append(inv_fact[-1] * inv[i] % P)

def C(n, k):
	return fact[n] * inv_fact[k] % P * inv_fact[n - k] % P

def cat(n):
	return fact[2 * n] * inv_fact[n] % P * inv_fact[n + 1] % P
cat_arr = list(map(cat, range(0, 5001)))

@functools.lru_cache(maxsize=None)
def f(x):
	ret = 0
	for n in range(1, x + 1):
		ret += C(x, n) * cat_arr[n] % P
		ret %= P
	return ret
t = int(input())
for _ in range(t):
	print(f(int(input())))


import sys
m = 5000
MOD = int(1000000000.0 + 9)

def main():
	arr = [1] * (m + 1)
	for i in range(1, m + 1):
		for j in range(i):
			arr[i] += arr[j] * arr[i - 1 - j]
			arr[i] %= MOD
	for _ in range(int(input())):
		n = int(input())
		print(arr[n] - 1)
sys.exit(main())


import sys
MAX_N = 5000
MOD = int(1000000000.0 + 9)

def main():
	ways = [1] * (MAX_N + 1)
	for i in range(1, MAX_N + 1):
		for j in range(i):
			ways[i] += ways[j] * ways[i - 1 - j]
			ways[i] %= MOD
	t = int(input())
	for _ in range(t):
		n = int(input())
		print(ways[n] - 1)
sys.exit(main())


import math
import os
import random
import re
import sys
import sys
MAX_N = 5000
MOD = int(1000000000.0 + 9)

def main():
	ways = [1] * (MAX_N + 1)
	for i in range(1, MAX_N + 1):
		for j in range(i):
			ways[i] += ways[j] * ways[i - 1 - j]
			ways[i] %= MOD
	t = int(input())
	for _ in range(t):
		n = int(input())
		print(ways[n] - 1)
sys.exit(main())


import sys
MAX_N = 5000
MOD = int(1000000000.0 + 9)

def main():
	ways = [1] * (MAX_N + 1)
	for i in range(1, MAX_N + 1):
		for j in range(i):
			ways[i] += ways[j] * ways[i - 1 - j]
			ways[i] %= MOD
	t = int(input())
	for _ in range(t):
		n = int(input())
		print(ways[n] - 1)
sys.exit(main())


import sys
MAX_N = 5000
MOD = int(1000000000.0 + 9)

def main():
	ways = [1] * (MAX_N + 1)
	for i in range(1, MAX_N + 1):
		for j in range(i):
			ways[i] += ways[j] * ways[i - 1 - j]
			ways[i] %= MOD
	t = int(input())
	for _ in range(t):
		n = int(input())
		print(ways[n] - 1)
sys.exit(main())


MAX_N = 5000
MOD = int(1000000000.0 + 9)
ways = [1] * (MAX_N + 1)
for i in range(1, MAX_N + 1):
	for j in range(i):
		ways[i] += ways[j] * ways[i - 1 - j]
		ways[i] %= MOD
t = int(input())
for _ in range(t):
	n = int(input())
	print(ways[n] - 1)


import sys
MAX_N = 5000
MOD = int(1000000000.0 + 9)

def main():
	ways = [1] * (MAX_N + 1)
	for i in range(1, MAX_N + 1):
		for j in range(i):
			ways[i] += ways[j] * ways[i - 1 - j]
			ways[i] %= MOD
	t = int(input())
	for k in range(t):
		n = int(input())
		print(ways[n] - 1)
sys.exit(main())


import sys
MAX_N = 5000
MOD = int(1000000000.0 + 9)

def main():
	ways = [1] * (MAX_N + 1)
	for i in range(1, MAX_N + 1):
		for j in range(i):
			ways[i] += ways[j] * ways[i - 1 - j]
			ways[i] %= MOD
	t = int(input())
	for _ in range(t):
		n = int(input())
		print(ways[n] - 1)
sys.exit(main())


import sys
MAX_N = 5000
MOD = int(1000000000.0 + 9)

def main():
	ways = [1] * (MAX_N + 1)
	for i in range(1, MAX_N + 1):
		for j in range(i):
			ways[i] += ways[j] * ways[i - 1 - j]
			ways[i] %= MOD
	t = int(input())
	for _ in range(t):
		n = int(input())
		print(ways[n] - 1)
sys.exit(main())


import sys
MAX_N = 5000
MOD = int(1000000000.0 + 9)

def main():
	ways = [1] * (MAX_N + 1)
	for i in range(1, MAX_N + 1):
		for j in range(i):
			ways[i] += ways[j] * ways[i - 1 - j]
			ways[i] %= MOD
	t = int(input())
	for _ in range(t):
		n = int(input())
		print(ways[n] - 1)
sys.exit(main())


import sys
MAX_N = 5000
MOD = int(1000000000.0 + 9)

def main():
	ways = [1] * (MAX_N + 1)
	for i in range(1, MAX_N + 1):
		for j in range(i):
			ways[i] += ways[j] * ways[i - 1 - j]
			ways[i] %= MOD
	t = int(input())
	for _ in range(t):
		n = int(input())
		print(ways[n] - 1)
sys.exit(main())


import sys
MAX_N = 5000
MOD = int(1000000000.0 + 9)

def main():
	ways = [1] * (MAX_N + 1)
	for i in range(1, MAX_N + 1):
		for j in range(i):
			ways[i] += ways[j] * ways[i - 1 - j]
			ways[i] %= MOD
	t = int(input())
	for _ in range(t):
		n = int(input())
		print(ways[n] - 1)
sys.exit(main())


import sys
MAX_N = 5000
MOD = int(1000000000.0 + 9)

def main():
	ways = [1] * (MAX_N + 1)
	for i in range(1, MAX_N + 1):
		for j in range(i):
			ways[i] += ways[j] * ways[i - 1 - j]
			ways[i] %= MOD
	t = int(input())
	for _ in range(t):
		n = int(input())
		print(ways[n] - 1)
sys.exit(main())


import sys
MAX_N = 5000
MOD = int(1000000000.0 + 9)

def main():
	ways = [1] * (MAX_N + 1)
	for i in range(1, MAX_N + 1):
		for j in range(i):
			ways[i] += ways[j] * ways[i - 1 - j]
			ways[i] %= MOD
	t = int(input())
	for _ in range(t):
		n = int(input())
		print(ways[n] - 1)
sys.exit(main())


import sys
MAX_N = 5000
MOD = int(1000000000.0 + 9)

def main():
	ways = [1] * (MAX_N + 1)
	for i in range(1, MAX_N + 1):
		for j in range(i):
			ways[i] += ways[j] * ways[i - 1 - j]
			ways[i] %= MOD
	t = int(input())
	for _ in range(t):
		n = int(input())
		print(ways[n] - 1)
sys.exit(main())


def solve():
	mod = 10 ** 9 + 9
	max_n = 5000
	dp = [1] * (max_n + 1)
	dp[1] = 2
	for i in range(2, max_n + 1):
		for j in range(i):
			dp[i] += dp[j] * dp[i - 1 - j]
			dp[i] %= mod
	return dp

def pascal(n):
	mod = 10 ** 9 + 9
	n += 1
	cache = [[0 for _ in range(n)] for _ in range(n)]
	for i in range(n):
		Cnk = 1
		for k in range(n):
			cache[i][k] = Cnk
			Cnk = Cnk * (i - k) % mod / (k + 1)
	return cache

def combination(a, b):
	b = min(b, a - b)
	numerator = 1
	denominator = 1
	c = 1
	for i in range(b):
		numerator *= a
		a -= 1
		denominator *= c
		c += 1
	return numerator / denominator

def precompute(n):
	mod = 10 ** 9 + 9
	dp = [0] * (n + 1)
	ar = [0] * (n + 1)
	combination_cache = pascal(n)
	dp[1] = 1
	dp[2] = 2
	for i in range(3, n + 1):
		dp[i] = 2 * dp[i - 1] % mod
		for j in range(1, i - 1):
			dp[i] += dp[j] * dp[i - 1 - j] % mod
	for i in range(1, n + 1):
		for j in range(1, i + 1):
			ar[i] = (ar[i] + dp[j] * combination_cache[i][j]) % mod
	return ar

def main():
	T = int(input())
	dp = solve()
	for _ in range(T):
		print(dp[int(input())] - 1)
main()


import sys
MAX_N = 5000
MOD = int(1000000000.0 + 9)

def main():
	ways = [1] * (MAX_N + 1)
	for i in range(1, MAX_N + 1):
		for j in range(i):
			ways[i] += ways[j] * ways[i - 1 - j]
			ways[i] %= MOD
	t = int(input())
	for _ in range(t):
		n = int(input())
		print(ways[n] - 1)
sys.exit(main())


import sys
MAX_N = 5000
MOD = int(1000000000.0 + 9)

def main():
	ways = [1] * (MAX_N + 1)
	for i in range(1, MAX_N + 1):
		for j in range(i):
			ways[i] += ways[j] * ways[i - 1 - j]
			ways[i] %= MOD
	t = int(input())
	for _ in range(t):
		n = int(input())
		print(ways[n] - 1)
sys.exit(main())


import sys
MAX_N = 5000
MOD = int(1000000000.0 + 9)

def main():
	ways = [1] * (MAX_N + 1)
	for i in range(1, MAX_N + 1):
		for j in range(i):
			ways[i] += ways[j] * ways[i - 1 - j]
			ways[i] %= MOD
	t = int(input())
	for _ in range(t):
		n = int(input())
		print(ways[n] - 1)
sys.exit(main())


import math
import os
import random
import re
import sys

def solve(n):
	import sys
MAX_N = 5000
MOD = int(1000000000.0 + 9)

def main():
	ways = [1] * (MAX_N + 1)
	for i in range(1, MAX_N + 1):
		for j in range(i):
			ways[i] += ways[j] * ways[i - 1 - j]
			ways[i] %= MOD
	t = int(input())
	for _ in range(t):
		n = int(input())
		print(ways[n] - 1)
sys.exit(main())
fptr = open(os.environ['OUTPUT_PATH'], 'w')
t = int(input().strip())
for t_itr in range(t):
	n = int(input().strip())
	result = solve(n)
	fptr.write(str(result) + '\n')
fptr.close()


import math
import os
import random
import re
import sys

def solve(n):
	import sys
MAX_N = 5000
MOD = int(1000000000.0 + 9)

def main():
	ways = [1] * (MAX_N + 1)
	for i in range(1, MAX_N + 1):
		for j in range(i):
			ways[i] += ways[j] * ways[i - 1 - j]
			ways[i] %= MOD
	t = int(input())
	for _ in range(t):
		n = int(input())
		print(ways[n] - 1)
sys.exit(main())
fptr = open(os.environ['OUTPUT_PATH'], 'w')
t = int(input().strip())
for t_itr in range(t):
	n = int(input().strip())
	result = solve(n)
	fptr.write(str(result) + '\n')
fptr.close()


import sys
MAX_N = 5000
MOD = int(1000000000.0 + 9)

def main():
	ways = [1] * (MAX_N + 1)
	for i in range(1, MAX_N + 1):
		for j in range(i):
			ways[i] += ways[j] * ways[i - 1 - j]
			ways[i] %= MOD
	t = int(input())
	for _ in range(t):
		n = int(input())
		print(ways[n] - 1)
sys.exit(main())


import sys
MAX_N = 5000
MOD = int(1000000000.0 + 9)

def main():
	ways = [1] * (MAX_N + 1)
	for i in range(1, MAX_N + 1):
		for j in range(i):
			ways[i] += ways[j] * ways[i - 1 - j]
			ways[i] %= MOD
	t = int(input())
	for _ in range(t):
		n = int(input())
		print(ways[n] - 1)
sys.exit(main())


import sys
MAX_N = 5000
MOD = int(1000000000.0 + 9)

def main():
	ways = [1] * (MAX_N + 1)
	for i in range(1, MAX_N + 1):
		for j in range(i):
			ways[i] += ways[j] * ways[i - 1 - j]
			ways[i] %= MOD
	t = int(input())
	for _ in range(t):
		n = int(input())
		print(ways[n] - 1)
sys.exit(main())


import math
import os
import random
import re
import sys
import sys
MAX_N = 5000
MOD = int(1000000000.0 + 9)

def main():
	ways = [1] * (MAX_N + 1)
	for i in range(1, MAX_N + 1):
		for j in range(i):
			ways[i] += ways[j] * ways[i - 1 - j]
			ways[i] %= MOD
	t = int(input())
	for _ in range(t):
		n = int(input())
		print(ways[n] - 1)
sys.exit(main())


import sys
MAX_N = 5000
MOD = int(1000000000.0 + 9)

def main():
	ways = [1] * (MAX_N + 1)
	for i in range(1, MAX_N + 1):
		for j in range(i):
			ways[i] += ways[j] * ways[i - 1 - j]
			ways[i] %= MOD
	t = int(input())
	for _ in range(t):
		n = int(input())
		print(ways[n] - 1)
sys.exit(main())


import math
import os
import random
import re
import sys
MAX_N = 5000
MOD = int(1000000000.0 + 9)

def main():
	ways = [1] * (MAX_N + 1)
	for i in range(1, MAX_N + 1):
		for j in range(i):
			ways[i] += ways[j] * ways[i - 1 - j]
			ways[i] %= MOD
	t = int(input())
	for _ in range(t):
		n = int(input())
		print(ways[n] - 1)
sys.exit(main())
t = int(input().strip())
for t_itr in range(t):
	n = int(input().strip())
	result = solve(n)
	fptr.write(str(result) + '\n')
fptr.close()


import sys
MAX_N = 5000
MOD = int(1000000000.0 + 9)

def main():
	ways = [1] * (MAX_N + 1)
	for i in range(1, MAX_N + 1):
		for j in range(i):
			ways[i] += ways[j] * ways[i - 1 - j]
			ways[i] %= MOD
	t = int(input())
	for _ in range(t):
		n = int(input())
		print(ways[n] - 1)
sys.exit(main())


import sys
MAX_N = 5000
MOD = int(1000000000.0 + 9)

def main():
	ways = [1] * (MAX_N + 1)
	for i in range(1, MAX_N + 1):
		for j in range(i):
			ways[i] += ways[j] * ways[i - 1 - j]
			ways[i] %= MOD
	t = int(input())
	for _ in range(t):
		n = int(input())
		print(ways[n] - 1)
sys.exit(main())