시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 0 0 0 0.000%

문제

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.

예제 입력 1

025

예제 출력 1

1525

예제 입력 2

222

예제 출력 2

NIE