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.

The only input line contains the number n of the sectors of the round table (6 ≤ n ≤ 10⁹).