--이것은 my TIP

import sys
input = sys.stdin.readline
def operation(a,b):
return [
[(a[0][0]*b[0][0]+ a[0][1]*b[1][0])%1000000007,
(a[0][0]*b[0][1] +a[0][1]*b[1][1])%1000000007],
[(a[1][0]* b[0][0]+a[1][1]*b[1][0])%1000000007,
(a[1][0]*b[0][1] +a[1][1]*b[1][1])%1000000007]
]
def matrix(m,n):
if 1==n: return m
half =matrix(m, n//2)
half =operation(half,half)
if n %2==1: half =operation(half,[[1,1],[1,0]])
return half
n= int(input()); print(matrix([[1,1],[1,0]],n)[0][1]) if n !=0 else print(0)

언젠가, 알고리즘을 풀다보면 재귀로는 못 푸는 문제를 마주하게 될 겁니다. fibonacci를 예로 들어보면, 재귀가 너무 시간을 많이 잡아 먹어서 나중에는 DP로 구현하게 될 겁니다. (아마도 상향식?) 그러나, n에 DP로도 시간 안에 못 풀 정도로 매ㅐㅐㅐ우 큰 수가 주어지면 다른 방법을 찾아야겠죠. 분할을 써서 성능 좋은 코드를 구현하면 됩니다.
일단은 이 문제에는 굳이 이렇게 구현하지 않아도 됩니다.
이렇게 분할 쓰면 n이 too much 커도 아주 빠르게 값을 구할 수 있습니다.
도움이 되었길 바랍니다.

해당 코드는 문제 조건과 약간 다릅니다. (복붙하면 안 되니까) I am 세밀해요~