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

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

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

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

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

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