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



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



Входные данные

Для каждого теста строка будет содержать целое число i от 0 до 10^8 включительно, для которого необходимо вычислить значение Fi-го числа Фибоначчи Fi.

Данные считывать до конца входного файла.

Выходные данные

Большие числа Фибоначчи получить довольно не сложно, поэтому, когда ответ состоит более чем из 8 цифр, выведите только первые и последние 4 цифры ответа, разделенные на две части многоточием ("...")