Двоичные палиндромы 2

Ваша задача — найти i-е неотрицательное целое число, которое является двоичным палиндромом.

Двоичный палиндром — это число, которое в двоичной системе счисления читается одинаково как справа налево, так и слева направо. Например, числа 5, 7, 9 и 21 являются двоичными палиндромами, тогда как числа 4, 10 и 11 — нет.

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

На первой строке вводится число i.

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

Выведите i-е неотрицательное целое число, являющееся двоичным палиндромом, по модулю 1000000007.

Примеры

Оценивание

50% — i ≤ $10^5$

50% — i ≤ $10^{18}$