Знову Фібоначчі!
"Навіщо використовувати підпрограму, якщо можна швидше просто надрукувати?"
Вауг Рокосц
У математиці числа Фібоначчі задаються наступною послідовністю: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, … . За визначенням, перших два числа послідовності Фібоначчі це 0 і 1, а всі наступні числа знаходяться як сума двох попередніх. У математичних термінах послідовність F_n чисел Фібоначчі визначається рекуретно F_{n }= F_{n-1}+F_{n-2} з заданими початковими значеннями F_0 = 0 і F_1 = 1.
За заданим індексом i числа Фібоначчі Вам потрібно обчислити відповідне значення F_i.
Вхідні дані
Вхідні дані складаються з декількох рядків. Кожен рядок містить єдине ціле число i (0 ≤ i < 1000), яке є номером числа Фібоначчі. Вхідні дані слід читати до кінця файлу.
Вихідні дані
Для кожного рядка, отриманого на вході, виведіть у окремому рядку відповідне значення F_i.