원탁 위 이웃한 합이 0이 아닌 경우의 수

원탁에 $N$명의 학생이 같은 간격으로 둘러앉아 있다. 각 학생은 빈 종이를 한 장씩 들고 있다. 학생들은 집합 $S=\{1,-1,2,-2\}$에서 원소를 하나씩 골라 자신의 종이에 쓴다. 이웃한 어떤 두 학생이 쓴 수의 합도 $0$이 되지 않는 경우의 수를 구하시오.

첫째 줄에 학생의 수를 나타내는 양의 정수 $N$이 주어진다. $(1\leq N\leq 10^{18})$

어떠한 이웃한 두 학생이 쓴 수의 합도 $0$이 되지 않는 경우의 수를 $10^{9}+3\ (=23\times 307\times 141623)$으로 나눈 나머지를 출력한다.