19587번 - 객실 배치

문제

성민이는 한 층에 2개의 객실이 있는 N층짜리 호텔을 운영하고 있다. (물리적으로 어떻게 가능한지는 무시하도록 하자)

각 호실은 자연수 번호를 가지고 있으며, 100으로 나눈 몫은 층수를 나타내고, 나머지는 1 또는 2이다. 한 층에 있는 두 방은 나머지가 서로 다르다. 나머지가 같으면서 몫이 1 차이 나는 두 방은 위아래로 인접하게 배치되어 있다. 예를 들어 1층에는 101호실과 102호실, 2층에는 201호실과 202호실이 존재한다.

어느 날 정부에서 전염병의 악화로 인한 “사회적 거리두기”를 선포하면서, 성민이는 호텔에 투숙하려는 고객들을 안내할 때 좀 더 경각심을 두고 조심스럽게 안내해야 한다.

호텔에서 객실을 배정할 때, 아래와 같은 조건들을 고려해야 한다.

1. 사회적 거리를 두기 위해, 같은 층에 고객을 동시에 배치하면 안 된다. 예를 들어 101호와 102호에 동시에 고객을 배치할 수 없다.
2. 전염병은 공기를 통해 퍼질 수 있기 때문에, 고객을 위아래로 인접하게 배치하면 안 된다. 예를 들어 101호와 201호에 동시에 고객을 배치할 수 없다.

N층의 호텔을 운영하는 성민이가 고객을 배치할 수 있는 경우의 수는 몇 가지일까?

입력

성민이가 운영하는 호텔의 층수인 정수 N이 입력으로 주어진다. (1 ≤ N ≤ 10¹⁸)

출력

성민이가 객실에 고객을 배치할 수 있는 경우의 수를 10⁹ + 7로 나눈 나머지를 출력한다.

제한

힌트