ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Open Ural FU Championship 2011

About     Problems     Submit solution     Judge status     Standings
Contest is over

A. Very Wealthy Mole

Time limit: 1.0 second
Memory limit: 64 MB
— What would you like to do in the meantime, wealthy moles?
— What if we make some calculations?
— That's a good idea!

From the Soviet animated film Thumbelina
One very wealthy mole knows only nonnegative integers. He can perform three operations on his abacus:
  1. obtain the number 2x from a number x;
  2. obtain the number 2x + 1 from a number x;
  3. obtain the number ⌊x/2⌋ (the integer part of x divided by 2).
Each morning the mole chooses a pair of integers x and y such that 1 ≤ x < y ≤ 2l − 1 and, during the day, obtains the number y from the number x by performing a sequence of operations on his abacus. The mole is good at arithmetics, so he always uses the shortest sequence of operations sufficient for obtaining the number y from the number x.
How many abacus operations will the mole perform in total until he exhausts all pairs of integers in the range from 1 to 2l − 1?

Input

The only line contains the integer l (2 ≤ l ≤ 1018).

Output

Find the number of abacus operations that the mole will perform and output this number modulo 109 + 7.

Sample

inputoutput
2
4

Notes

On the first day the mole obtains the number 2 from the number 1 by performing the first operation. On the second day the mole obtains the number 3 from the number 1 by performing the second operation. On the third day he obtains the number 3 from the number 2 by performing the third and then the second operation.
Problem Author: Denis Dublennykh
Problem Source: Open Ural FU Championship 2011
To submit the solution for this problem go to the Problem set: 1862. Very Wealthy Mole