一列に n 個のマスが並んでおり、各マスには 1～(n-1) のいずれかの数字が書かれています。
この一列のマスに対して、書かれている数字の数だけ左右に移動します。
このとき、進む方向は「左」「右」を交互に繰り返します。

最初、左端から右向きにスタートして、右端のマスに到達するような数字の配置を考えます。
なお、右端のマスに到達した時点で終了するため、右端のマスは0とします。
また、左端のマスより左、右端のマスより右には移動できないため、
そのような数字の配置はできないものとします。

例えば、以下のマスのように配置されていると、図のように移動します。

このように、右端に到達できる数字の配置のうち、すべてのマスでちょうど一度ずつ止まるものが何通りあるかを求めてください。
例えば、n = 6 の場合は、上記の左図の他に右図のようなパターンがあり、全部で5通りです。
なお、n は12以下の整数とします。

【入出力サンプル】
標準入力
6

標準出力
5

【解答方法】
■挑戦言語は下記のプログラム言語選択で選択可能なものであれば何でもＯＫです！
1)自分の書いたプログラム言語を選択
2)解答欄にソースコードを記入
3)送信前に「提出前に確認」ボタンをクリック（構文エラーがないかどうかチェックできます）
4)「解答コードは正常に実行されました」というメッセージを確認の上、「解答を送信」ボタンで解答してください。

■この問題にはテストケースが5つ用意されています。すべてに通れば正解です！


【採点について】
・採点は「ideone」を使ってプログラムを実行し、標準入力および標準出力のテストケースと照合して正誤を判定します
・各言語の標準入力と標準出力はこちらを参考にしてください
・標準入力の最終行の改行はあり／なし両方に対応してください
※なおCodeIQで使用しているideoneは企業版のため、webで公開されているコンシューマー版ideoneとは
　対応言語・バージョン・挙動が異なる場合があります。
　企業版ideoneの対応バージョンは、「提出前チェック」の結果とともに表示されます。