이카수

시간 제한8초메모리 제한512 MB

요약

정수 좌표 사이를 1 또는 2만큼 점프해 이동할 때 특정 정수 좌표를 피하는 경로 수가 될 수 있는 수들을 크기순으로 나열하고, K번째 수를 구한다.

문제

수직선 위의 정수 좌표에 고양이 Taro의 집, 당근, 토끼 Hanako의 집이 이 순서대로 놓여 있다. 점 $x$ 에 있는 오징어는 한 번의 점프로 $x + 1$ 또는 $x + 2$ 로 이동할 수 있다.

오징어가 Taro의 집에서 Hanako의 집까지 당근이 놓인 좌표에 멈추지 않고 가는 경로의 수를 구하려 했지만, Taro의 집, 당근, Hanako의 집의 좌표를 모르기 때문에 구할 수 없었다. 그래서 대신 경로의 수로 가능한 수를 모두 나열하기로 했다.

어떤 Taro의 집, 당근, Hanako의 집의 배치에 대해 오징어의 경로 수가 되는 정수를 이카수라고 부르자. $K$ 번째로 작은 이카수 (1-indexed)를 mod 1,000,000,007로 구하라.

입력은 이카의 형식으로 주어진다:

$K$

$K$ 번째로 작은 이카수를 1,000,000,007로 나눈 나머지를 한 줄에 출력하라.