1025 - Sequence

Time Limit: 1s Memory Limit: 128MB

Submissions: 313 Solved: 61
Description
Consider the special sequence of numbers, which satisfies the following requirements: a[0] = 0; a[1] = 1; for every i = 1, 2, 3, ... a[2*i] = a[i]; a[2*i+1] = a[i] + a[i+1]; Your task is easy, write a program which for a given value of N (0 < N < 1018) finds the Nth number of the sequence.
Input
Only one number N.
Output
For every N in the input write the Nth number of the sequence.
Sample Input
0
1
2
Sample Output
0
1
1
Hint
Source
ACman