hibye1217   3년 전

더 나은 번역 있으면 알려주세요 :blobcry:

문제

수직선의 정수 좌표점 위에 고양이의 집, 당근 1개, 토끼의 집이 이 순서대로 놓여있습니다.

$ x $에 위치해있는 오징어는, 한 번의 점프로 $ x+1 $ 또는 $ x+2 $로 이동할 수 있습니다.

당신은 오징어가 고양이의 집에서 토끼의 집까지 당근이 있는 위치에 멈추지 않고 가는 경로가 몇 개나 되는지 궁금했지만, 집의 위치나 당근의 위치를 알아낼 수가 없었습니다. 그래서, 경로의 개수로 가능한 모든 수들을 모아서 오징어 수라고 부르기로 했습니다.

다르게 말하자면, 어떤 수 $ N $이 오징어 수라는 것은, 오징어가 위 규칙을 만족하면서 갈 수 있는 경로의 개수가 정확히 $ N $개가 되는 집과 당근의 배치가 존재한다는 것을 의미합니다.

$ K $가 주어질 때, $ K $번째로 작은 오징어 수를 $ 1\,000\,000\,007 $로 나눈 나머지를 출력하세요.

입력

첫째 줄에 정수 $ K $가 주어집니다. ($ 1 \le K \le 10^{18} $)

출력

$ K $번째 오징어 수를 $ 1\,000\,000\,007 $로 나눈 나머지를 출력합니다.

추가 설명

아래는 오징어 수와, 오징어 수가 아닌 수의 예시입니다.

  • $ 5 $: (고양이의 집, 당근, 토끼의 집) = (3, 8, 9)에 위치해 있다면, 오징어가 정확히 $ 5 $가지의 경로를 가지게 되므로 오징어 수입니다.
  • $ 7 $: 집과 당근의 위치를 어떻게 잡아도 오징어가 정확히 $ 7 $가지의 경로를 가지게 할 수 없으므로 오징어 수가 아닙니다.

댓글을 작성하려면 로그인해야 합니다.