ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

1763. Expert Flea

Time limit: 0.5 second
Memory limit: 64 MB
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.
Problem illustration
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

inputoutput
6
12
Problem Author: Igor Chevdar
Problem Source: The 14th Urals Collegiate Programing Championship, April 10, 2010