F. Уравнения математической магии
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
Колоссально! — воскликнул горбоносый. — Программист! Нам нужен именно программист.
Аркадий и Борис Стругацкие, Понедельник начинается в субботу

Изучая книгу «Уравнения математической магии» Роман Ойра-Ойра и Кристобаль Хунта обнаружили интересное уравнение: $$$a - (a \oplus x) - x = 0$$$ для заданого $$$a$$$, где знаком $$$\oplus$$$ обозначено побитовое исключающее ИЛИ (XOR) двух чисел (эта операция обозначается как ^ или xor во многих современных языках программирования). Поскольку данное уравнение предназначалось для решения на машине Алдан-3, все вычисления производились над целыми неотрицательными числами по модулю $$$2^{32}$$$. Ойра-Ойра быстро нашел $$$x$$$, являющееся решением, однако Кристобалю Хунте результат Ойры-Ойры показался недостаточно интересным, поэтому он спросил коллегу, сколько всего существует решений данного уравнения. Так как все вычисления производятся по модулю $$$2^{32}$$$, Кристобаля Хунту интересует количество таких решений $$$x$$$, что $$$0 \leq x \lt 2^{32}$$$. Такая задача оказалась для Ойры-Ойры слишком сложной, поэтому он обратился за помощью к Вам.

Входные данные

В первой строке задано одно целое число $$$a$$$ ($$$0 \leq a \leq 2^{32} - 1$$$).

Выходные данные

Выведите одно целое число — количество неотрицательных решений уравнения.

Примеры
Входные данные
0
Выходные данные
2
Входные данные
2
Выходные данные
4
Входные данные
4294967295
Выходные данные
4294967296
Примечание

Определим операцию побитового ИЛИ (XOR). Пусть даны два целых неотрицательных числа $$$x$$$ и $$$y$$$, рассмотрим их двоичные записи (возможно с ведущими нулями): $$$x_k \dots x_2 x_1 x_0$$$ и $$$y_k \dots y_2 y_1 y_0$$$. Здесь $$$x_i$$$ это $$$i$$$-й бит числа $$$x$$$, а $$$y_i$$$ это $$$i$$$-й бит числа $$$y$$$. Пусть $$$r = x \oplus y$$$ — результат операции XOR над числами $$$x$$$ и $$$y$$$. Тогда двоичной записью $$$r$$$ будет $$$r_k \dots r_2 r_1 r_0$$$, где:

$$$$$$ r_i = \left\{ \begin{aligned} 1, ~ \text{если} ~ x_i \ne y_i \\ 0, ~ \text{если} ~ x_i = y_i \end{aligned} \right. $$$$$$

В первом примере решениями уравнения являются $$$0$$$ и $$$2147483648 = 2^{31}$$$, так как $$$0 - (0 \oplus 0) - 0 = 0 - 0 - 0 = 0$$$ и $$$0 - (0 \oplus 2147483648) - 2147483648 = -4294967296 = -2^{32} = 0$$$ по модулю $$$2^{32}$$$.

Во втором примере решениями уравнения являются $$$0$$$, $$$2$$$, $$$2147483648 = 2^{31}$$$ и $$$2147483650 = 2^{31} + 2$$$.

В третьем примере решениями являются все $$$x$$$, для которых выполнено $$$0 \leq x \lt 2^{32}$$$.