Fibonacci

길이가 최대 18인 숫자열이 주어질 때, 십진수 피보나치 수 F_k가 그 문자열로 끝나는 k를 10^100 미만에서 하나 찾아 출력하고, 없으면 NIE를 출력한다.

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

문제 설명

예제2

문제

Liczby Fibonacciego definiujemy następująco:

F0 = 0, F1 = 1, Fm = Fm−1 + Fm−2 dla m ≥ 2.

Twoim zadaniem jest znalezienie takiego k, że zapis dziesiętny liczby Fk (bez zer wiodących) kończy się zadanym ciągiem cyfr.

입력

W jedynym wierszu wejścia znajduje się napis złożony z n cyfr c1c2...cn (1 ≤ n ≤ 18, 0 ≤ ci ≤ 9).

출력

Jeśli istnieje choć jedna taka liczba całkowita k, że 0 ≤ k < 10100 oraz zapis dziesiętny liczby Fk kończy się ciągiem cyfr c1c2...cn, to na wyjście należy wypisać dowolną taką liczbę. W przeciwnym razie na wyjście należy wpisać słowo NIE.