問題一覧 > 通常問題

No.660 家を通り過ぎないランダムウォーク問題

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 38
作問者 : しらっ亭しらっ亭 / テスター : 夕叢霧香(ゆうむらきりか)夕叢霧香(ゆうむらきりか)
2 ProblemId : 1889 / 出題時の順位表
問題文最終更新日: 2018-03-03 00:01:12

問題文

雪子さんは東西に無限に続く1次元の道に立っています。 雪子さんは現在地点から $N$ 歩東に進んだ場所にある自宅に帰ろうとしています。

しかし、雪子さんは酔っ払ってしまっており、足元がおぼつきません。ですので、歩こうとすると $1$ 歩東または西に進みます。

雪子さんは $2 \times N$ 歩を超えて歩くと、疲れてしまって歩くのをやめてしまい、帰宅できません。

雪子さんが自宅の位置に到達すると、必ず歩くのをやめて自宅に入ります。それ以降は歩くことをしません。

雪子さんが疲れてしまう前、すなわち $2 \times N$ 歩以下の歩数で自宅に入る歩き方として、有り得るものの総数を出力してください。この値はとても大きくなるので、$10^9+7$ で割った余りを答えてください。

入力

N

$ 1 \le N \le 2 \times 10^5 $

出力

帰宅するまでの歩き方の総数を $10^9+7$ で割った余りを出力して、改行してください。

サンプル

サンプル1
入力
2
出力
3

4歩以内で帰宅できる歩き方として、以下の3通りがあります。

  • → →
  • → ← → →
  • ← → → →

以下の歩き方は、2歩目の時点で自宅に入るため、あり得ない事に注意してください。

  • → → ← →
  • → → → ←
サンプル2
入力
6
出力
144

沢山ありますね。

サンプル3
入力
10
出力
9878

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