| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 556 | 204 | 147 | 45.794% |
5차원 세계에 사는 구사과는 크기가 2 × 2 × 2 × 2 × n인 초콜릿을 가지고 있다.
오늘은 초콜릿을 잘라서 크기가 1 × 1 × 1 × 1 × 2인 초콜릿을 총 8n개 만들려고 한다. 자르는 방법의 수를 구하는 프로그램을 작성하시오.
초콜릿의 방향은 중요하지 않다. 즉, 1 × 1 × 1 × 2 × 1, 2 × 1 × 1 × 1 × 1도 가능한 크기이다.
첫째 줄에 n(1 ≤ n ≤ 109)이 주어진다.
첫째 줄에 방법의 수를 109+7로 나눈 나머지를 출력한다.
1
272
2
589185
3
930336768