3×N 벽 타일 채우기

$3 \times N$ 크기의 벽을 $2 \times 1$ 타일과 $1 \times 2$ 타일로 빈틈없이 채우는 경우의 수를 구한다. 타일끼리 겹치거나 벽 밖으로 나가면 안 된다. 두 모양은 각각 원하는 개수만큼 쓸 수 있다.

첫째 줄에 $N$이 주어진다. ($1 \le N \le 10^{18}$)

첫째 줄에 경우의 수를 $10^9 + 7$로 나눈 나머지를 출력한다.