問題一覧 > 通常問題

No.523 LED

レベル : / AI推定難易度 : 750 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 256
作問者 : hirakich1048576 / テスター : butsurizuki
お気に入りにしたユーザー ProblemId : 1117 / 自分の提出
問題文最終更新日: 2026-06-25 01:30:35
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 165 (順位表) の他の問題:

Problem Statement

F is bored and sometimes comes up with interesting ideas. Today, F came up with another one.
The idea is to prepare N green LEDs numbered from 1 to N, and to try every possible procedure that turns all of them red.
The procedure works as follows.

  • Each LED has one switch.
  • Pressing the switch makes a green LED light up yellow and a yellow LED light up red.
  • No operation can be performed on a red LED.
Being a busybody, you decide to calculate the number of operation procedures for F.
When considering the LEDs targeted in the procedure, output the number of operation procedures modulo 1000000007.

Input

N

The value of N (1 ≤ N ≤ 107) is given on one line.

Output

Output the number of possible operation procedures modulo 1000000007 on one line.

Sample

Sample 1
Input
2
Output
6

For N=2, the operation procedures are the following

  • "1 to yellow", "2 to yellow", "1 to red", "2 to red"
  • "1 to yellow", "2 to yellow", "2 to red", "1 to red"
  • "2 to yellow", "1 to yellow", "1 to red", "2 to red"
  • "2 to yellow", "1 to yellow", "2 to red", "1 to red"
  • "1 to yellow", "1 to red", "2 to yellow", "2 to red"
  • "2 to yellow", "2 to red", "1 to yellow", "1 to red"
for a total of 6 ways.

Sample 2
Input
495
Output
498394413

Sample 3
Input
114514
Output
556245728

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