*— 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 2
*x* from a number *x*;
- obtain the number 2
*x* + 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* ≤ 2^{l} − 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 2^{l} − 1?

### Input

The only line contains the integer *l* (2 ≤ *l* ≤ 10^{18}).

### Output

Find the number of abacus operations that the mole will perform and
output this number modulo 10^{9} + 7.

### Sample

### 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