Послідовність Фібоначчі - це така послідовність, у якій кожен елемент дорівнює сумі двох попередніх, за винятком перших двох елементів F0 і F1, які відповідно є нулем і одиницею.

Чому дорівнює значення n-го числа Фібоначчі?

Вхідні дані

Кожний рядок містить ціле число i (0 ≤ i ≤ 108), для якого необхіно обчислити значення i-го числа Фібоначчі Fi.

Вихідні дані

Великі числа Фібоначчі отримати досить нескладно, тому, коли відповідь містить більше ніж 8 цифр, виведіть лише перші і останні 4 цифри відповіді, розділені на дві частини трикрапкою ("...") - див. приклад.