Knights' tournaments were quite popular in the Middle Ages. A lot of boys were dreaming of becoming a knight, while a lot of girls were dreaming of marrying a knight on a white horse.

In this problem we consider one of these tournaments. 

Let's us call a tournament binary, if it runs according to the scheme described below:

- Exactly N knights take part in the tournament, N=2K for some integer K > 0.
		
- Each knight has a unique skill called strength, described as an integer from the interval [1, N].
		
- Initially, all the knights are standing in a line, waiting for a battle. Since all their strengths are unique, each initial configuration can be described as a permutation of numbers from 1 to N.
		
- There are exactly K rounds in the tournament, 2K - i + 1 knights take part in the i'th round. The K'th round is called the final.
		
- The i'th round runs in the following way: for each positive integer j ≤ 2K - i happens a battle between a knight on the 2∙j'th position and a knight on the 2∙j+1'th position. The strongest of two continues his tournament, taking the j'th position on the next round, while the weakest of two is forced to leave.
		
- The only knight, who has won K rounds, is the winner. The only knight, who has won K - 1 rounds, but lost the final, is the runner-up.   
	

As you can see from the scheme, the winner is always the same, an initial configuration doesn't change anything. So, your task is to determine chances of each knight to appear in the final.

Formally, for each knight you need to count the number of initial configurations, which will lead him to the final. Since the number can be extremly huge, you are asked to do all the calculations under modulo 109 + 9.

-----Input-----

The first line contains the only integer K, denoting the number of rounds of the tournament.

-----Output-----
Output should consist of 2K lines. The i'th line should contain the number of initial configurations, which lead the participant with strength equals to i to the final.

-----Constraints-----
1 ≤ K < 20


-----Examples-----
Input:
1

Output:
2
2

Input:
2

Output:
0
8
16
24

-----Explanation-----

In the first example we have N=2 knights. Let's consider each initial configuration that could appear and simulate the tournament.

(1, 2) -> (2)

(2, 1) -> (2)

In the second example we have N=4 knights. Let's consider some initial configurations that could appear and simulate the tournament.

(1, 2, 3, 4) -> (2, 4) -> (4)

(3, 2, 4, 1) -> (3, 4) -> (4)

(4, 1, 3, 2) -> (4, 3) -> (4)

Difficulty: MEDIUM_HARD
Tags: Combinatorics

Mathematics

Starter code:

Solutions:
from itertools import *
from math import factorial

def bruteforce():
	k = 3
	n = 2 ** k
	freq = dict()
	for i in range(1, n + 1):
		freq[i] = 0
	for p in permutations(range(1, n + 1)):
		p = list(p)
		original = [x for x in p]
		while len(p) != 2:
			temp = []
			for i in range(0, len(p), 2):
				temp.append(max(p[i], p[i + 1]))
			p = temp
		freq[p[0]] = freq[p[0]] + 1
		freq[p[1]] = freq[p[1]] + 1
	for i in range(1, n + 1):
		print(i, freq[i])
MOD = 10 ** 9 + 9

def binomial(n, k):
	if n < 0 or k < 0 or k > n:
		return 0
	return factorial(n) // factorial(k) // factorial(n - k)

def main():
	k = int(input())
	n = 2 ** k
	bucket_size = n // 2
	fact = 1
	for i in range(1, bucket_size + 1):
		fact = fact * i % MOD
	C = 2 * fact ** 2 % MOD
	for i in range(1, bucket_size):
		print(0)
	binomial_term = 1
	num_factor = bucket_size
	den_factor = 1
	for i in range(bucket_size, n + 1):
		print(binomial_term * C % MOD)
		binomial_term *= num_factor
		binomial_term *= pow(den_factor, MOD - 2, MOD)
		binomial_term %= MOD
		num_factor += 1
		den_factor += 1
main()


(n, p) = (int(input()), 10 ** 9 + 9)
m = 1 << n - 1
tmp = 1
for i in range(1, m + 1):
	tmp = tmp * i % p
tmp = tmp ** 2 * 2 % p
ans = '0\n' * (m - 1) + str(tmp) + '\n'
(inv, t) = ([1] * (m + 3), 1)
for i in range(m, 1 << n):
	tmp = tmp * i % p * inv[t] % p
	ans += str(tmp) + '\n'
	t += 1
	inv[t] = -(p // t) * inv[p % t] % p
print(ans, end='')


mod = 1000000009
import math
K = int(input())
N = 2 ** K
temp1 = N // 2
fact = math.factorial(N / 2 - 1) % mod
div = fact ** 2 * temp1 * N % mod
temp2 = 1
for i in range(1, N + 1):
	if i < N / 2:
		print('0')
	else:
		print(div)
		div = div * pow(temp2, mod - 2, mod) % mod * temp1 % mod
		temp1 += 1
		temp2 += 1


import sys

def C(a, b):
	x = F[a]
	y = pow(F[b] * F[a - b], 10 ** 9 + 7, 10 ** 9 + 9)
	return x * y % (10 ** 9 + 9)
k = int(input())
n = 2 ** k
MOD = 10 ** 9 + 9
F = [0] * 1000001
F[0] = 1
F[1] = 1
for i in range(2, 1000001):
	F[i] = F[i - 1] * i
	F[i] %= MOD
Ans = ''
for i in range(1, n + 1):
	if i < n // 2:
		Ans += '0\n'
		continue
	ans = C(i - 1, n // 2 - 1) * 2
	ans %= MOD
	ans *= F[n // 2]
	ans %= MOD
	ans *= F[n // 2]
	ans %= MOD
	Ans += str(ans) + '\n'
sys.stdout.write(Ans)


mod = 1000000009
import math
k = int(input())
n = 2 ** k
t1 = n // 2
f = math.factorial(n / 2 - 1) % mod
d = f ** 2 * t1 * n % mod
t2 = 1
for i in range(1, n + 1):
	if i < n / 2:
		print('0')
	else:
		print(d)
		d = d * pow(t2, mod - 2, mod) % mod * t1 % mod
		t1 += 1
		t2 += 1


import sys
MOD = 1000000009
K = int(sys.stdin.readline())
N = 1 << K
M = 1 << K - 1
factorial = [1]
for n in range(1, N + 1):
	factorial.append(n * factorial[-1] % MOD)
for _ in range(1, M):
	print(0)
base = 2 * M * factorial[M] % MOD
for i in range(M, N):
	c = factorial[i - 1] * pow(factorial[i - M], MOD - 2, MOD)
	print(c * base % MOD)
print(factorial[N])


MOD = 1000000009
fac = [0] * 1100000
fac[0] = 1

def fact(n):
	global fac
	if fac[n] != 0:
		return fac[n]
	fac[n] = n * fact(n - 1) % MOD
	return fac[n]

def pow_2(k):
	res = 1
	while k > 0:
		res <<= 1
		k -= 1
	return res

def comb(n, r):
	res = fact(n) * pow(fact(r) * fact(n - r) % MOD, MOD - 2, MOD) % MOD
	return res

def range_prod(lo, hi):
	if lo + 1 < hi:
		mid = (hi % MOD + lo % MOD) % MOD // 2
		return range_prod(lo % MOD, mid % MOD) % MOD * range_prod(mid + 1, hi) % MOD
	if lo == hi:
		return lo % MOD
	return lo % MOD * (hi % MOD) % MOD

def tree_factorial(n):
	if n < 2:
		return 1
	if fac[n] != 0:
		return fac[n]
	fac[n] = range_prod(1, n)
	return fac[n]

def mod_div(a, b, p):
	return a % p * (pow(b, p - 2, p) % p) % p
k = int(input())
nr = pow_2(k - 1) - 1
total = pow_2(k)
per = total // 2
for i in range(nr):
	print(0)
con_res = 2 * (tree_factorial(per) * tree_factorial(per)) % MOD % MOD
mul = 1
count = 1
for i in range(nr, total):
	fin_res = mul * con_res % MOD
	mul = mul % MOD * ((i + 1) % MOD) % MOD
	mul = mod_div(mul, count, MOD)
	count += 1
	print(fin_res)


fact = {}
fact[0] = 1
mod = 1000000009
m = {}
k = int(input())
t = 2 ** k
i = t // 2
j = t - 1
m[t] = 1
while i > 0:
	m[j] = m[j + 1] * i % mod
	j -= 1
	i -= 1
tfact = 1
f = 1
for f in range(1, t // 2):
	tfact = tfact * f % mod
fact[f] = tfact
for g in range(f + 1, t):
	tfact = tfact * g % mod
	fact[g] = tfact
for i in range(1, t // 2):
	print(0)
const = 2 * (t // 2) % mod
j = t // 2
for i in range(1, t // 2 + 2):
	print(const * m[j] * fact[j - 1] % mod)
	j += 1