Послідовність Фібоначчі

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

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

Вхідні дані

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

Вихідні дані

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

Приклади