— 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:
- obtain the number 2x from a number x;
- obtain the number 2x + 1 from a number x;
- 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