No.140 みんなで旅行

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 67
作問者 : kmjpkmjp
8 ProblemId : 251 / 出題時の順位表
問題文最終更新日: 2015-11-14 17:47:27

問題文

\(N\)組の夫婦、計\((2\times N)\)人で旅行に行くことにした。
\((2\times N)\)人は幾つかのグループに別れ、それぞれグループメンバの車で移動することになった。

各夫婦は皆大型車を持っており、グループに1台車があればグループ全員が移動できる。
ただし、各夫婦が車を使わせてくれるのは、夫婦が同一のグループにいる場合だけである。
すなわち、各グループが無事に車で旅行に行くためには、グループに1組以上夫婦のペアが含まれていなければならない。

条件を満たすグループの分け方が何通りあるかを答えよ。
答えは非常に大きくなる可能性があるので、\(10^9+7\)の剰余を取った値を答えること。

入力

\(N\)

\(1 \le N \le 555\)

出力

無事に皆で旅行ができるグループの分け方が何通りあるかを1行で答えよ。

なお、想定解における最大ケースの実行時間はPythonで1.2秒である。

サンプル

サンプル1
入力
2
出力
2

2組の夫婦をA-a,B-bとする。(Aとaが夫婦、Bとbが夫婦)

  • 1グループで移動するケースは{ AaBb }の1通り
  • 2グループで移動するケースは{ Aa, Bb }の1通り
合計2通りである。
{ Ab, aB }のような組み合わせはどちらのグループも車が使えないため、条件を満たさない。
サンプル2
入力
3
出力
11

3組の夫婦をA-a,B-b,C-cとする。

  • 1グループで移動するケースは{ AaBbCc }の1通り
  • 2グループで移動するケースは以下の9通り
    • { AaBb, Cc }, { AaCc, Bb }, { Aa, BbCc }
    • { AaC, Bbc }, { Aac, BbC }, { ABb, aCc }, { aBb, ACc }, { AaB, bCc }, { Aab, BCc }
  • 3グループで移動するケースは{ Aa, Bb, Cc }の1通り
合わせて11通り。
サンプル3
入力
123
出力
658991534

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