시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 10 6 4 50.000%

문제

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

1

예제 출력 1

272

예제 입력 2

2

예제 출력 2

589185

예제 입력 3

3

예제 출력 3

930336768

출처