No.790 ちきんの括弧並べ

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 90
作問者 : severrabaenseverrabaen / テスター : KuskeKuske
3 ProblemId : 2667

問題文

ちきんは'('の文字を$N$個、')'の文字も$N$個持っています('は文字に含まれません)。ちきんはこの2種類の文字を全て使用した対応の取れた括弧列が全部で何通り作れるか知りたくなりました。ただし、対応の取れた括弧列とは問題文末尾の定義を満たしている必要があります。ちきんの代わりに全部で何通りの対応の取れた括弧列が作れるかを出力してあげてください。

定義:
・空文字列は正しい括弧列の条件を満たす。
・文字列$s$が正しい括弧列の条件を満たすなら、($s$)は正しい括弧列である。
・文字列$s$と$t$がどちらも正しい括弧列の条件を満たすなら、$s$と$t$を連結した文字列は正しい括弧列である。

入力

$N$

1行目にちきんが所持している括弧の個数$N(1 \le N \le 13)$が与えられます。

出力

対応の取れた括弧列の個数を出力し、最後に改行してください。

サンプル

サンプル1
入力
2
出力
2

(())、()()の2通りのみが対応の取れた括弧列です。例えば、())(は括弧が完全には閉じられていないので対応の取れた括弧列ではありません。

サンプル2
入力
3
出力
5

((()))、()()()、()(())、(())()、(()())の5つが条件を満たします。例えば、())(()はダメです。定義を満たしていません。
なお、3番目と4番目は違う文字列としてカウントされることに注意してください。

サンプル3
入力
11
出力
58786

多いですね。

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。