問題文

正の整数 $N$ が与えられます。 $2$ つの整数 $u,v(0≦u,v≦N)$ であって、ある非負整数 $a,b$ が存在して、$a$ $xor$ $b=u$、$a+b=v$ となるようなものが何通りあるかを求めてください。 ここで、$xor$ はビットごとの排他的論理和を表します。 なお、答えは非常に大きくなることがあるので、$10^9+7$ で割った余りを求めてください。

制約

• $1≦N≦10^{18}$

入力

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

$N$

出力

ありうる $2$ 数の組が何通りあるかを求め、$10^9+7$ で割った余りを出力せよ。

入力例 1

3

出力例 1

5

$u,v$ としてありうるものは、以下の $5$ 通りです。

• $u=0,v=0$（ $a=0,b=0$ とすると、$0$ $xor$ $0=0$、$0+0=0$ となります。）

• $u=0,v=2$（ $a=1,b=1$ とすると、$1$ $xor$ $1=0$、$1+1=2$ となります。）

• $u=1,v=1$（ $a=1,b=0$ とすると、$1$ $xor$ $0=1$、$1+0=1$ となります。）

• $u=2,v=2$（ $a=2,b=0$ とすると、$2$ $xor$ $0=2$、$2+0=2$ となります。）

• $u=3,v=3$（ $a=3,b=0$ とすると、$3$ $xor$ $0=3$、$3+0=3$ となります。）

入力例 2

1422

出力例 2

52277

入力例 3

1000000000000000000

出力例 3

787014179