제목 추천 좀

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

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

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