시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 (추가 시간 없음) 1024 MB 111 60 55 58.511%

문제

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

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

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

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

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

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

입력

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

출력

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

예제 입력 1

1

예제 출력 1

3

1층 호텔이면 101호에 배치한 경우, 102호에 배치한 경우, 아무 호실에도 배치하지 않는 경우, 총 3가지 경우를 생각할 수 있다.

예제 입력 2

5

예제 출력 2

99