색깔 하노이 탑

하노이 탑 게임은 3개의 기둥과 크기가 모두 다른 여러 장의 원판을 이용하는 게임이다. 처음에는 1번 기둥에 원판이 크기 순서대로 쌓여 있으며, 큰 원판이 아래에 오도록 놓여 있다. 다음 규칙을 지키면서 모든 원판을 3번 기둥으로 옮겨야 한다.

• 작은 원판 위에 큰 원판을 올릴 수 없다.
• 한 번에 1개의 원판만 옮길 수 있다.

이 규칙을 바탕으로 원판의 색깔이 두 가지인 하노이 탑 게임을 만들려고 한다.

처음에는 1번 기둥에 위에서부터 차례대로 크기 1인 빨간 원판, 크기 1인 검은 원판, 크기 2인 빨간 원판, 크기 2인 검은 원판, ..., 크기 $N$인 빨간 원판, 크기 $N$인 검은 원판이 놓여 있다.

위의 규칙을 지키면서 원판을 옮겨 3번 기둥에 위에서부터 차례대로 크기 1인 빨간 원판, 크기 1인 검은 원판, 크기 2인 빨간 원판, 크기 2인 검은 원판, ..., 크기 $N$인 빨간 원판, 크기 $N$인 검은 원판이 놓이도록 해야 한다. 원판을 최소로 옮길 때 총 몇 번 옮겨야 하는가?

첫 번째 줄에 정수 $N$($1 \le N \le 10^6$)이 주어진다.

첫 번째 줄에 원판의 최소 이동 횟수를 출력한다. 수가 커질 수 있으므로, 최소 이동 횟수를 $10^9 + 7$로 나눈 나머지를 출력한다.

원판의 크기가 같다면 색과 상관없이 어떤 원판을 위에 올려놓아도 된다. 다만 최종 상태는 위에서부터 빨강 원판, 검정 원판, 빨강 원판, 검정 원판, ... 순이어야 한다.