Задача 38513. Equations of Mathematical Magic

Colossal! — exclaimed the hunchback. — Programmer! We need a programmer.
Arkady and Boris Strugatsky, Monday starts on Saturday
Studying the book "Equations of Mathematical Magic" Roman Oira-Oira and Cristobal Junta discovered an interesting equation: a−(a⊕x)−x=0 for a given a, where   ⊕   stands for bitwise exclusive OR (XOR) of two numbers (this operation is denoted as ^ or xor in many modern programming languages). Since this equation was intended to be solved on the Aldan-3 machine, all calculations were performed on non-negative integers modulo 2³². Oira-Oira quickly found x, which is a solution, but Cristobal Junta found Oira-Oira's result not interesting enough, so he asked a colleague how many solutions there are to this equation. Since all calculations are done modulo 2³², Cristobal Junto is interested in the number of solutions x such that 0 ≤ x≤ 2³². Such a task turned out to be too difficult for Oira-Oira, so he turned to you for help.

Input
The first line contains a single integer a (0 ≤ a ≤ 2³²−1).

Imprint
Print a single integer — the number of non-negative solutions of the equation.

Note
Let's define the bitwise OR (XOR) operation. Let two non-negative integers x and y be given, consider their binary representations (possibly with leading zeros): x_k...x₂x₁x₀ and y_k...y₂y₁y₀ . Here x_i is the i-th bit of x and y_i is the i-th bit of y. Let r=x⊕y — the result of an XOR operation on the numbers x and y. Then the binary representation of r is r_k...r₂r₁r₀, where:
In the first example, the solutions to the equation are 0 and 2147483648=2³¹, because 0−(0⊕0)−0=0−0−0=0 and 0−(0⊕ 2147483648)− 2147483648=−4294967296=−2³²=0 modulo 2³².

In the second example, the solutions to the equation are 0, 2, 2147483648=2³¹ and 2147483650=2³¹+2.

In the third example, the solutions are all x for which 0 ≤ x≤ 2³².
 

Examples

#	Input	Output
1	0	2
2	2	4
3	4294967295	4294967296