問題文

ちゃろー、センパイ。
今、めぐる、ちょたクエっていう同人ゲームやってるんですけど、クリア後のエクストラダンジョンが酷いんですよね…。
友達の病気を治すために、愛らしいキャラクターのcucumberに頼んで、魔法少女になって課題をこなすってストーリーなんですけど、この課題がすっごく面倒なんです！

課題の迷宮の第 $N$ 階層は、$N$ 段の三角形からできているような形なんですけど…、って言ってもわからないですよね。
簡単に描くとこんなのですね。

この迷宮の第 $N$ 階層の中で、決められたルートを通ると次の階層への階段が現れるんですけど、決められたルートが何なのかヒントが全くないので全部試さないといけないんですよね…。
今までの傾向から言うと、決められたルートって、単純多角形からなるルートなんですけど、それでも、ルートの数が多すぎて…。
あ、単純多角形って、辺が交差しない多角形ですね。ARC037Dを見るとセンパイでもよくわかると思いますよ！
あーもぉ、一体何個ぐらい試さないといけないルートがあるんですかね…！？

入力

$N$

$1 \leq N \leq 12$

出力

第 $N$ 階層におけるルートの数を出力して下さい、センパイ！
ルートはどこから初めても最初の場所に戻ってくればいいですから、単純多角形の数と同じなんですよね。

サンプル

1

1

2

11

5

128967