[ABC050D] Xor Sum

## 题目描述 给出正整数$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}$

[problemUrl]: https://atcoder.jp/contests/abc050/tasks/arc066_b 正の整数 $ 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 $ で割った余りを出力せよ。

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