2022 하계모각코 6주차 결과

mem={0:0, 1:1}
mod=1000000007
def fib(t):
    if t in mem:
        return mem[t]
    else:
        if t%2==0:
            a=fib(t//2-1)%mod
            b=fib(t//2)%mod
            f=((2*a+b)*b)%mod
        else:
            f=(fib((t+1)//2)%mod)**2+(fib((t-1)//2)%mod)**2
        mem[t]=f%mod
        return f%mod
t=int(input())
print((fib(t)%mod)*(fib(t+1)%mod)%mod)

피보나치 수열을 푸는데 시간이 조금 오래 걸렸습니다. 행렬을 구하는데 어려움이 조금 있었습니다.