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

1862. 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?


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


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




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