A flea has jumped onto a round table used in the popular quiz “What? Where?
When?” In this quiz, the questions are put inside envelopes lying on the
sectors of the round table. A panel of experts has to answer questions chosen
by a roulette pointer from those lying on the table. The flea wants to read all
the questions in advance and thus have more time to find the answers.
The round table is divided into n sectors numbered clockwise from 1 to n.
The flea has jumped onto the first sector. From this sector it can either run
to an adjacent sector or jump across two sectors (for example, if the table is
divided into 12 sectors, then in one move the flea can get to sectors 2, 4, 10,
and 12). The flea wants to visit each sector exactly once and return to the
first sector, from which it will jump down to the floor and run away to think
about the questions. Find the number of ways in which the flea can complete its
journey.
Input
The only input line contains the number n of the sectors of the round table
(6 ≤ n ≤ 109).
Output
Output the number of ways to visit each of the sectors exactly once
and return to the first sector modulo 109 + 9.
Sample
Problem Author: Igor Chevdar
Problem Source: The 14th Urals Collegiate Programing Championship, April 10, 2010