No.523 LED

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 170
作問者 : hirakich1048576hirakich1048576 / テスター : butsurizukibutsurizuki
6 ProblemId : 1117 / 出題時の順位表
問題文最終更新日: 2017-06-25 01:44:21

問題文

Fは暇であり、時々面白いことを思いつく。今日もFはあることを思いついた。
1 から N の番号が割り振られた緑のLEDを N 個用意し、その全てを赤にする手順を、有り得るもの全て試すというものである。
手順は以下の通りである。

  • 各LEDには、スイッチが1つある。
  • スイッチを押すと、緑のLEDは黄に、黄のLEDは赤に発光する。
  • 赤のLEDに対して操作を施すことはできない。
おせっかいなあなたは、Fのために操作手順の数を算出することにした。
手順に関して対象となるLEDを考えるとき、操作手順の数を1000000007で割ったあまりを出力せよ。

入力

N

N (1 ≤ N ≤ 107) の値が1行で与えられる。

出力

有り得る操作手順の数を1000000007で割ったあまりを一行に出力せよ。

サンプル

サンプル1
入力
2
出力
6

N=2 のときの操作手順は、

  • 「1を黄に」「2を黄に」「1を赤に」「2を赤に」
  • 「1を黄に」「2を黄に」「2を赤に」「1を赤に」
  • 「2を黄に」「1を黄に」「1を赤に」「2を赤に」
  • 「2を黄に」「1を黄に」「2を赤に」「1を赤に」
  • 「1を黄に」「1を赤に」「2を黄に」「2を赤に」
  • 「2を黄に」「2を赤に」「1を黄に」「1を赤に」
の6通りである。

サンプル2
入力
495
出力
498394413

サンプル3
入力
114514
出力
556245728

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