시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB162927365.179%

문제

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

입력

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

출력

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

예제 입력 1

5

예제 출력 1

244

출처

School > 세종과학예술영재학교 > SASA Programming Contest 2023 G번