401370: GYM100418 J Lucky tickets

Everyone knows that in less than a month the Ice Hockey World Championship will start in Minsk. But few of the guests of our city know that this is the reason why the new tickets and system of accounting were introduced in the public transport (which at the moment is unstable due to some structural flaws). It is obvious that the new tickets require the new formula for determining whether they are lucky or not. It is such an important task that it was given to the authors of BSUIR Open problems. After months of deliberation and disputes the following formula was proposed: a ticket is lucky if it is divisible by the number of symbol 1 in the binary representation. And then the authors thought that the number of these lucky tickets would be too big. Therefore, they asked you for help. Determine the quantity of lucky tickets with numbers from the interval [1..N].

The first line contains the integer number N (1 ≤ N ≤ 10¹⁹).

Output the number of lucky tickets.

153

42