题目描述

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

输入格式

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

$N$

输出格式

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

题目大意

题目描述

给出正整数$N$.

求出整数对$u$和$v$ $(0≤u,v≤N)$的数目，使得存在两个非负整数$a$和$b$满足$a\ xor\ b = u$和$a\ +\ b= v$。这里，$xor$表示按位异或。 要求对答案取模$10^9 + 7$。

输入输出格式

输入格式

一个正整数$N$

输出格式

满足条件的$u,v$的个数，对$10^9+7$取模

数据范围：

$N<=10^{18}$

3

5

1422

52277

1000000000000000000

787014179

提示

制約

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

Sample Explanation 1

$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$ となります。）