No.234 めぐるはめぐる (4)

レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 128 MB / 通常問題
タグ : / 解いたユーザー数 11
作問者 : LayCurseLayCurse
1 ProblemId : 536 / 出題時の順位表
問題文最終更新日: 2015-11-14 17:49:02

問題文

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

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

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

入力

$N$

$1 \leq N \leq 12$

出力

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

サンプル

サンプル1
入力
1
出力
1
サンプル2
入力
2
出力
11

ARC037Dの最初のサンプルと同じ問題ですかね?

サンプル3
入力
5
出力
128967

提出するには、Twitter または、GitHubもしくは右上の雲マークをクリックしてアカウントを作成してください。