피보나치 수의 제곱의 합

• 제목 그대로 피보나치 수의 제곱의 합을 구하면 된다.
• 피보나치 수 (Fibonacci numbers)에서 언급했듯이 F(0)^2+F(1)^2+…+F(n)^2 = F(n)*F(n+1)이 성립한다.
• 따라서, n번째와 n+1번째 피보나치 수를 구해서 곱한 값을 출력하면 끝. 시간복잡도는 O(logn)

"""Solution code for "BOJ 11440. 피보나치 수의 제곱의 합".

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

Tags: [Fibonacci]
"""

from teflib import combinatorics

MOD = 1_000_000_007


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


if __name__ == '__main__':
    main()

• Dependency: teflib.combinatorics.fibonacci