5차원 세계에 사는 구사과는 크기가 2 × 2 × 2 × 2 × n인 초콜릿을 가지고 있다.</p>

오늘은 초콜릿을 잘라서 크기가 1 × 1 × 1 × 1 × 2인 초콜릿을 총 8n개 만들려고 한다. 자르는 방법의 수를 구하는 프로그램을 작성하시오.

초콜릿의 방향은 중요하지 않다. 즉, 1 × 1 × 1 × 2 × 1, 2 × 1 × 1 × 1 × 1도 가능한 크기이다.

입력 형식

첫째 줄에 n(1 ≤ n ≤ 10⁹)이 주어진다.

출력 형식

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

예제 입력 1

1

예제 출력 1

272

예제 입력 2

2

예제 출력 2

589185

예제 입력 3

3

예제 출력 3

930336768