We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. All Contests
  2. HourRank 2
  3. Guga's Function

Guga's Function

Guga has a function where is a number of interesting segments in the binary representation of .

A segment is interesting if it has the following properties:

  • The first and last characters are 's.
  • All the other characters are 's.
  • It has a length of at least .

For example, the binary representation of is , and it contains two interesting segments: and . So .

Guga defined a variable by following equation:

.

Given the value of can you help Guga to calculate . As the answer can be very big, calculate just modulo .

Input Format

A single line of input contains one number, .

Constraints:

For full score:
For score:

Output Format

Print the value of % in a single line.

Sample Input 1

4

Sample Output 1

5

Sample Input 2

5

Sample Output 2

17

Explanation

For the first sample:






For all others numbers in the range , the values are .