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=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.
The first line contains the only integer K, denoting the number of rounds of the tournament.
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.
Constraints1 ≤ K < 20
Input: 1 Output: 2 2
Input: 2 Output: 0 8 16 24
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)
|Tags||combinatorics, easy, kostya_by, march14|
|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, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.