Informatica Online Judge

  삼각 하노이(L) [1205 / 04B5]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 234   Total Tried : 300


The Champion of this Problem (C++) : tlsdydaud1 - ms / 108byte
My Best Submission (C++) : N/A

[JKJeong 2015]

Background

삼각 하노이는 다음 그림과 같이 정삼각형 모양의 3개의 타워에 원판이 아래쪽 두 꼭짓점에 크기가 위에서부터 1, 2, ... , n인 원판이 놓여 있다.



이 예는 n이 2인 예이며, 모두 2n개의 원판이 있다.

이 게임의 목적은 일반적인 하노이 규칙 (한 번에 하나의 원판만 옮길 수 있으며, 작은 원판 위에 큰 원판을 올릴 수 없다.)을 지켜가면서 아래 그림과 같이 모두 위쪽 꼭짓점으로 모든 원판을 옮기는 것이다.



일반 하노이와 다른 점은 크기가 같은 원판위에는 서로 올릴 수 있다는 점이 다르다.

아래쪽 두 꼭짓점에 있는 원판의 수 n이 주어질 때, 2n개의 모든 원판을 위쪽으로 모두 옮기는 최소 횟수를 구하는 프로그램을 작성하시오.

Input

첫 번째줄에 원판의 수를 나타내는 정수 n이 입력된다.

[입력값의 정의역]
1 <= n <= 1,000,000

Output

모든 원판을 위쪽 꼭짓점으로 옮기는데 드는 최소 이동 횟수를 출력한다.단 값이 너무 커지기 때문에 1,000,000,007로 나눈 나머지를 출력한다.

IO Example

입력1
1

출력1
2

입력2
2

출력2
7

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]