условия

Вычислите n-й член последовательности, заданной формулами:

a2n = an ­+ an-1,
a2n+1 = an – an-1,
a0 = a1 = 1.
Входные данные
Вводится одно натуральное число n (1≤n≤1000).

Выходные данные
Вывести одно число an.

Примеры