피보나치 수의 마지막 13자리

1 이상 10^13 이하인 n이 주어질 때, n번째 피보나치 수의 마지막 13자리가 n과 같은 가장 작은 i를 찾고, 없으면 -1을 출력한다.

어려움8수학정수론이분 탐색아직 제출이 없습니다시간 제한2초메모리 제한512 MB

문제 설명

예제3

$F_n$ 을 $n$ 번째 피보나치 수라 하고, $G_n = F_n \bmod 10^{13}$ 이라고 하자. 즉 $G_n$ 은 $F_n$ 의 마지막 13자리다.

$n$ 이 주어졌을 때, $G_i = n$ 인 가장 작은 $i$ 를 찾는 프로그램을 작성하시오.

피보나치 수의 앞부분은 다음과 같다.

첫째 줄에 정수 $n$ ( $1 \le n \le 10^{13}$ )이 주어진다.

$G_i = n$ 인 가장 작은 $i$ 를 출력한다. 그러한 $i$ 가 없으면 -1을 출력한다. 답은 $10^{13}$ 보다 클 수 있다.