Stern's Diatomic Sequence Evaluation

Little Bai and Little Lan attend a mathematics class together. After class, their teacher assigns them a homework problem: derive the closed-form expression for the following sequence defined by the recurrence:

$$a_0=0,\quad a_1=1,\quad a_{2i}=a_i,\quad a_{2i+1}=a_i+a_{i+1}.$$

Little Bai, a math enthusiast, quickly found the general term. To show off his achievement and prove that he indeed obtained the formula, he proposes the following challenge: Little Lan will give a positive integer n, and Little Bai will respond with the value of \(a_n\). If Little Bai can supply the correct answer quickly even when n is very large, it proves that he has truly mastered the formula. However, Little Lan is not strong in math and cannot verify Bai's answer. As a friend of Little Lan, your task is to help her verify Little Bai's response by computing \(a_n\) efficiently.

Note: The sequence defined above is known as Stern's diatomic sequence, and a very efficient iterative method exists to calculate \(a_n\) using the binary representation of n.

inputFormat

The input consists of a single line containing a positive integer n (where n can be as large as allowed by the problem constraints). If n equals 0, note that \(a_0=0\).

outputFormat

Output a single integer representing the value of \(a_n\) according to Stern's diatomic sequence recurrence.

sample

0

0