Вычислите n-й член последовательности, заданной формулами:
a
2n = a
n + a
n-1,
a
2n+1 = a
n – a
n-1,
a
0 = a
1 = 1.
Входные данные
Вводится одно натуральное число n (1≤n≤1000).
Выходные данные
Вывести одно число a
n.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
|
3
|