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