객실 배치
시간 제한1초메모리 제한1024 MB
각 층에 방이 두 개씩 있는 N층 호텔에서 같은 층이나 수직으로 인접한 방에 손님을 동시에 배치하지 않는 경우의 수를 10^9+7로 나눈 나머지를 구한다.
문제
성민이는 한 층에 객실이 2개씩 있는 N층짜리 호텔을 운영한다. (물리적으로 어떻게 가능한지는 생각하지 않기로 하자.)
각 객실에는 자연수 번호가 붙어 있다. 번호를 100으로 나눈 몫은 층수를, 나머지는 1 또는 2를 나타낸다. 같은 층에 있는 두 객실의 나머지는 서로 다르다. 나머지가 같고 몫이 1만큼 차이나는 두 객실은 위아래로 인접해 있다. 예를 들어 1층에는 101호와 102호가, 2층에는 201호와 202호가 있다.
어느 날 정부가 전염병 악화를 이유로 "사회적 거리두기"를 선포하자, 성민이는 호텔에 투숙하려는 고객을 안내할 때 더 조심해야 한다.
객실을 배정할 때 다음 조건을 지켜야 한다.
- 사회적 거리를 두기 위해, 같은 층에 고객을 동시에 배치하면 안 된다. 예를 들어 101호와 102호에 동시에 고객을 배치할 수 없다.
- 전염병은 공기를 통해 퍼질 수 있으므로, 고객을 위아래로 인접하게 배치하면 안 된다. 예를 들어 101호와 201호에 동시에 고객을 배치할 수 없다.
N층짜리 호텔을 운영하는 성민이가 고객을 배치할 수 있는 경우의 수는 몇 가지일까?
입력
성민이가 운영하는 호텔의 층수인 정수 N이 입력으로 주어진다. (1 ≤ N ≤ 10^18)
출력
성민이가 객실에 고객을 배치할 수 있는 경우의 수를 10^9 + 7로 나눈 나머지를 출력한다.