Binary Tournament

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
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=2^{K} 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, 2^{K  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 ≤ 2^{K  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 runnerup.
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 10^{9} + 9.
Input
The first line contains the only integer K, denoting the number of rounds of the tournament.
Output
Output should consist of 2^{K} 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)
Author:  kostya_by 
Editorial  http://discuss.codechef.com/problems/BINTOUR 
Tags  combinatorics, easy, kostya_by, march14 
Date Added:  21012014 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions