Parsa finds himself in the velvet-lit backroom of the Infinity Casino, where a game of pure logic awaits. At the table sits the legendary Masked Dealer, who presents Parsa with a game known in whispers as XORcade.

On the table are n numbered chips, labeled from 0 to n - 1. The dealer gives Parsa a challenge: Pick a number x between 0 and n - 1. For every chip i in that same range, compute i ⊕ x, where ⊕ denotes bitwise XOR. If every result also falls in the range 0 to n - 1, you win. If even one result is outside that range, the house wins.

Parsa wants to play smart, so he asks you: "How many such numbers x are there between 0 and n - 1 that let Parsa win?"

Help him win the game — and claim half of the prize for yourself.

Input

A single integer n (1 ≤ n ≤ 10¹⁸), the number of chips.

Output

Print how many different values of x (0 ≤ x ≤ n - 1) there are, such that Parsa can win the game.

Sample Input:

20

Sample Output:

4