Binary Palindromes 2#9578

Binary Palindromes 2

1 second

64 megabytes

Very easy

Your task is to find the $i$ -th non-negative binary palindrome.

A binary palindrome is a number that reads the same forwards and backwards in the binary numeral system. For example, the numbers $5$ , $7$ , $9$ , and $21$ are binary palindromes, whereas the numbers $4$ , $10$ , and $11$ are not.

Input

The first line contains the integer: $i$ .

Output

Output the $i$ -th non-negative binary palindrome modulo $1000000007$ on a single line.

Examples

Example 1

Loading

Example 2

Loading

Example 3

Loading

Example 4

Loading

Scoring

$50%$ — $i \leq 1 0^{5}$ i \le 10^5

$50%$ — $i \leq 1 0^{18}$ i \le 10^{18}

i \leq 1 0^{5}

i \leq 1 0^{18}