피보나치 수

시간 제한2초메모리 제한512 MB

요약

길이 n(1 이상 18 이하)의 숫자열이 주어질 때, F_k의 끝자리가 이 숫자열과 일치하는 k를 10^100 미만에서 찾고, 없으면 NIE를 출력합니다.

문제

피보나치 수는 다음과 같이 정의한다.

$F_0 = 0$ , $F_1 = 1$ , $F_m = F_{m-1} + F_{m-2}$ ( $m \ge 2$ )

앞자리에 0을 붙이지 않은 십진수 표기가 주어진 숫자열로 끝나는 $k$ 를 찾아라.

첫 줄에 $n$ 개의 숫자로 이루어진 문자열 $c_1c_2\ldots c_n$ 이 주어진다 ( $1 \le n \le 18$ , $0 \le c_i \le 9$ ).

$0 \le k < 10^{100}$ 을 만족하는 정수 $k$ 중에서 $F_k$ 의 십진수 표기가 $c_1c_2\ldots c_n$ 으로 끝나는 값이 하나라도 존재하면, 그러한 $k$ 를 아무거나 하나 출력한다. 존재하지 않으면 NIE를 출력한다.