#188. 数列第n项

数列第n项

说明

在有一个数列的通项公式如下图所示,需要你求出an的值。 

a0=0,a1=1; 

对于任意的i>0: a(2i)=a(i) 

a(2i+1)=a(i)+a(i+1) 。

输入格式

1行:输入一个整数n

输出格式

1行:输出数列的第n项的值

样例

3
2