Informatica Online Judge

  초보들의 하노이타워 [1483 / 05CB]

Time Limit(Test case) : 1000 (ms)
Number of users who solved : 96   Total Tried : 466


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

[JKJeong 2016]

Background

하노이 타워 문제는 잘 알고 있을 것이다.

1번 기둥에 있는 n개의 원판을 3번 기둥으로 모두 옮기는 것이다.

하노이 타워를 최단으로 풀기 위해서는 귀납적인 사고를 해야한다.

하지만 이번에 하노이 타워를 해결하고자 하는 경곽이는 하노이타워에 대해서 초보이기 때문에 최소 횟수라는 규칙을 제외했고, 그 외 규칙은 원래와 같다.

- 한 번에 하나의 원판만 옮길 수 있다.
- 작은 원판위에 큰 원판을 올릴 수 없다.


경곽이에게 주어진 원판을 옮기는 횟수는 최대 m회이다.

기둥이 3개인 기본 하노이 타워에서 원판이 n개 원판을 m회 이내로 옮길 수 있는 경우의 수를 구해보자.

이 게임을 진행하는 경곽이는 같은 상태를 여러번 반복할 수도 있다. 즉, 같은 상태를 반복해도 m회 이내라면 허용된다.

단, 마지막 상태에 도달했다면 그 즉시 게임은 종료된다.

Input

첫 번째 줄에 원판의 수 n과 최대 옮기는 횟수 m이 공백으로 구분되어 입력된다.

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

Output

가능한 모든 경우의 수를 출력한다.

값이 매우 커질 수 있기 때문에 결과를 10억 7(1,000,000,007)로 나눈 나머지를 출력한다.

IO Example

입력1
3 6

출력1
0

입력2
3 7

출력2
1

입력3
2 5

출력3
10

* 설명
입력 1은 3개짜리 하노이에서 6회만에 옮길 수 있는 방법은 없으므로 0
입력 2는 3개의 최솟값이 7이고 이는 유일하므로 방법은 1가지
입력 3에서 2개의 경우

- 횟수가 3일 경우 1가지
- 횟수가 4일 경우 2가지
- 횟수가 5일 경우 7가지 ( 이 경우는 그림으로 그려서 확인하면 알 수 있다. )

따라서 10가지가 된다.

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