Ваша задача – знайти i-тий цілий невід’ємний двійковий паліндром.

Двійковий паліндром – це число, яке у двійковій системі числення читається справа наліво і зліва направо однаково. Наприклад, числа 5, 7, 9, 21 – є двійковими паліндромами, а числа 4, 10, 11 – ні.

Вхідні дані:

В першому рядку вводиться число: i.

Вихідні дані:

В єдиному рядку потрібно вивести i-тий цілий невід’ємний двійковий паліндром за модулем 1000000007.

Оцінювання:

50% - i ≤ 105

50% - i ≤ 1018