제목 추천 좀

아직 제출이 없습니다시간 제한1초메모리 제한1024 MB

문제 설명

예제1

문제

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

입력

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

출력

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