13727번 - 5차원 구사과 초콜릿

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 ≤ 10⁹)이 주어진다.

첫째 줄에 방법의 수를 10⁹+7로 나눈 나머지를 출력한다.