Cho $a$ là một số $SUMXOR$ với b khi:

• $a+b=a\oplus b$
• $0\le a\le b$
• b ≤ 10^18

Lưu ý: $\oplus$ là kí hiệu của toán tử $XOR$

Cho một số nguyên $b$, đếm số lượng số $a$ là số $SUMXOR$ với $b$

Kết quả: Là số lượng số $a$ là số $SUMXOR$ với $b$

Ví dụ:

Input

10

Output

4