====== 피보나치 수 3 ======

===== 풀이 =====
  * [[ps:피보나치 수]]를 계산하는 문제. [[ps:problems:boj:11444]]와 n의 범위까지 동일하지만, 모듈러가 다르다.
  * 모듈러가 10^k 형태인데, 이 경우에는 피사노 주기가 15*10^(k-1)이 된다고 알려져 있다. 따라서 이 문제에서의 피사노 주기는 1,500,000이고, (n % 1,500,000)번째의 피보나치 수만 계산하는 것으로 문제를 바꿀 수 있다. 이렇게 범위를 줄여서 풀 경우에는 O(n) 알고리즘으로도 풀이가 가능하다
  * 하지만, 그냥 [[ps:problems:boj:11444]]과 동일하게 O(logn) 알고리즘을 사용하면 피사노 주기를 활용하지 않고도 더 빠르게 풀수 있다.
    * 물론 피사노 주기를 활용해서 범위를 줄여놓고서 O(logn)알고리즘을 쓰면 좀더 빨라지지만, 이미 충분히 빨라서 큰 차이는 안난다. 시간이 100ms정도에서 70ms정도로 줄어드는 정도.

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 2749. 피보나치 수 3".

- Problem link: https://www.acmicpc.net/problem/2749
- Solution link: http://www.teferi.net/ps/problems/boj/2749

Tags: [Fibonacci]
"""

from teflib import combinatorics

MOD = 1_000_000
PISANO_PERIOD = 1_500_000


def main():
    n = int(input())
    print(combinatorics.fibonacci(n % PISANO_PERIOD, MOD))


if __name__ == '__main__':
    main()
</dkpr>
  * Dependency: [[:ps:teflib:combinatorics#fibonacci|teflib.combinatorics.fibonacci]]

{{tag>BOJ ps:problems:boj:골드_2}}