시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 (추가 시간 없음) | 1024 MB | 420 | 195 | 167 | 53.355% |
성민이는 한 층에 2개의 객실이 있는 N층짜리 호텔을 운영하고 있다. (물리적으로 어떻게 가능한지는 무시하도록 하자)
각 호실은 자연수 번호를 가지고 있으며, 100으로 나눈 몫은 층수를 나타내고, 나머지는 1 또는 2이다. 한 층에 있는 두 방은 나머지가 서로 다르다. 나머지가 같으면서 몫이 1 차이 나는 두 방은 위아래로 인접하게 배치되어 있다. 예를 들어 1층에는 101호실과 102호실, 2층에는 201호실과 202호실이 존재한다.
어느 날 정부에서 전염병의 악화로 인한 “사회적 거리두기”를 선포하면서, 성민이는 호텔에 투숙하려는 고객들을 안내할 때 좀 더 경각심을 두고 조심스럽게 안내해야 한다.
호텔에서 객실을 배정할 때, 아래와 같은 조건들을 고려해야 한다.
N층의 호텔을 운영하는 성민이가 고객을 배치할 수 있는 경우의 수는 몇 가지일까?
성민이가 운영하는 호텔의 층수인 정수 N이 입력으로 주어진다. (1 ≤ N ≤ 1018)
성민이가 객실에 고객을 배치할 수 있는 경우의 수를 109 + 7로 나눈 나머지를 출력한다.
1
3
1층 호텔이면 101호에 배치한 경우, 102호에 배치한 경우, 아무 호실에도 배치하지 않는 경우, 총 3가지 경우를 생각할 수 있다.
5
99