Царь Камбис любит числа Фибоначчи. Напомним, что числа Фибоначчи определяются следующим образом: f0 = f1 = 1, а для любого i ≥ 2: fi = fi - 1 + fi - 2.
Сегодня царь решил собрать новую армию, с количеством солдат, равным n-ому числу Фибоначчи. Помогите ему вычислить это число.
Выходные данные
Выведите одно число — n-ое число Фибоначчи.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
|
2
|
|
2
|
1
|
1
|