이렇게 처음에 코드를 제출하였더니, 시간초과가 나서 질문글을 조금 살펴보았더니 15746으로 나눈 나머지를 저장해서 진행하면 해결이 됐다는 말을 보아서, 한번 코드를 

tmp[1] = (tmp[0] + tmp[1]) % 15746 

tmp[0] = (p2)%15746

이렇게 나눈 나머지를 저장하여 진행하였더니 통과하였습니다.

궁금한 것은

왜 연산과정은 두단계로 동일한데, 아니 오히려 나눈 나머지가 포함된 위의 정답식이 한단계 더 진행이 되고 코드가 진행되는데,

시간면에서 이득을 볼 수 있는건가요?

원래 코드의 dp()의 결과가 너무 크게 되어지고, 그걸 숫자로 나눠주는 작업이 더 복잡한 과정이라고 이해하면 되는건가요?

그리고 점화식을 구하는 특성방정식을 이용해서, 문제를 해결해봤는데 작은수에서의 답은 나오는데 10000정도만 넘어가도 오버플로우가 뜨더군요...

파이썬에서 오버플로우 나는거 처음 봤습니다. 뭐.. 이건 특성방정식 자체가 n제곱으로 대입이 되니까 큰수에서 오버플로우는 뜰 수 있는것 같습니다..