DivideSum

問題文

正の整数を定義域とする関数$f$が

$f(x)= \left \{ \begin{array}{l} x　　　(xが奇数のとき) \\ f(\frac{x}{2})　(xが偶数のとき) \end{array} \right.$

と定義されています。

正の整数 $n$ が入力として与えられます。

$\displaystyle\sum_{k=1}^{n} f(k)$

の値を$1000000007$で割った余りを求めてください。

制約

$1\leq n \leq 10^{12}$

入力

入力は以下の形式で標準入力から与えられる。

n

出力

答えを標準出力に1行で出力せよ。行末に改行を入れること。

入力例1

4

出力例1

6

$f(1)=1,　f(2)=f(1)=1,　f(3)=3,　f(4)=f(2)=f(1)=1$

となり、合計は $6$ です。

入力例2

123456789012

出力例2

449155048

$1000000007$で割った余りを出力してください。