====== 피보나치 수 6 ======

===== 풀이 =====
  * [[ps:피보나치 수]]를 계산하는 문제. n이 최대 10^18까지 들어오므로 O(n) 풀이로는 불가능. O(logn) 풀이를 사용해서 풀면 된다.
    * [[:ps:teflib:combinatorics#fibonacci|teflib.combinatorics.fibonacci]] 를 쓰면 된다.

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

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

Tags: [Fibonacci]
"""

from teflib import combinatorics

MOD = 1_000_000_007


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


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

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