N. Некрасивые двоичные числа

Число называется некрасивым, если его нельзя получить из другого натурального числа, прибавив к нему сумму его двоичных цифр — то есть количество единичных битов.

Например, $14 = 1110_2$ получается из $12 = 1100_2$: у двенадцати два единичных бита, и $12 + 2 = 14$. А вот $20$ так получить нельзя.

Первые пять некрасивых чисел: $1$, $4$, $6$, $13$, $15$. Посчитайте, сколько некрасивых чисел не превосходит $n$.

Одна строка содержит число $n$ ($1 \le n \le 10^7$).

Одно число — количество некрасивых чисел, не превосходящих $n$.