No.140 みんなで旅行
kmjp問題文最終更新日: 2015-11-14 17:47:27
問題文
\(N\)組の夫婦、計\((2\times N)\)人で旅行に行くことにした。
\((2\times N)\)人は幾つかのグループに別れ、それぞれグループメンバの車で移動することになった。
各夫婦は皆大型車を持っており、グループに１台車があればグループ全員が移動できる。
ただし、各夫婦が車を使わせてくれるのは、夫婦が同一のグループにいる場合だけである。
すなわち、各グループが無事に車で旅行に行くためには、グループに１組以上夫婦のペアが含まれていなければならない。
条件を満たすグループの分け方が何通りあるかを答えよ。
答えは非常に大きくなる可能性があるので、\(10^9+7\)の剰余を取った値を答えること。
入力
\(N\)
\(1 \le N \le 555\)
出力
無事に皆で旅行ができるグループの分け方が何通りあるかを１行で答えよ。
なお、想定解における最大ケースの実行時間はPythonで1.2秒である。
サンプル
サンプル1
入力
2
出力
2
2組の夫婦をA-a,B-bとする。(Aとaが夫婦、Bとbが夫婦)
- 1グループで移動するケースは{ AaBb }の1通り
- 2グループで移動するケースは{ Aa, Bb }の1通り
{ 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通り
サンプル3
入力
123
出力
658991534
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。