Informatica Online Judge

  삼각형 다리 건너기 (Small) [1173 / 0495]

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


The Champion of this Problem (C++) : gs19022 - 0ms / 187byte
My Best Submission (C++) : N/A

[koistudy.net (30th 김용석)]

Background

그림과 같이 양 변의 길이가 L인 이등변 직각 삼각형이 평면 위에 놓여있다.



이 이등변 직각 삼각형은 양 변의 길이가 1인 닮음 삼각형에 의해 그림처럼 분할 되어 있는 상태다.

경곽이는 꼭지점 A에서 꼭지점 B지점으로 1씩 움직이며 갈 수 있는 경우의 수를 다음과 같은 규칙에 따라 구하고자 한다.

꼭지점 A에서 꼭지점 B로 갈 때,

1) 한 번 움직일 때마다 1씩 움직이며 지나간 길을 돌아가지 않는다.
2) 이동할 수 있는 방향은, 북쪽, 동쪽, 남쪽, 북동쪽 방향 뿐이다.

Input

첫 번째 줄에 이등변 직각 삼각형의 양 변의 길이 L이 주어진다.

[입력값의 정의역]

1 <= L <= 200

Output

꼭지점 A에서 꼭지점 B로 이동할 수 있는 경우의 수를 10억 7로 나눈 나머지 값으로 출력한다.

IO Example

입력
2

출력
8

입력
4

출력
384

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