17758번 - Fibonacci 스페셜 저지다국어

Liczby Fibonacciego definiujemy następująco:

F₀ = 0, F₁ = 1, F_m = F_m−1 + F_m−2 dla m ≥ 2.

Twoim zadaniem jest znalezienie takiego k, że zapis dziesiętny liczby F_k (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 c₁c₂...c_n (1 ≤ n ≤ 18, 0 ≤ c_i ≤ 9).

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