/ 
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 600 点
問題文
正の整数 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
Score : 600 points
Problem Statement
You are given a positive integer N. Find the number of the pairs of integers u and v (0≦u,v≦N) such that there exist two non-negative integers a and b satisfying a xor b=u and a+b=v. Here, xor denotes the bitwise exclusive OR. Since it can be extremely large, compute the answer modulo 10^9+7.
Constraints
- 1≦N≦10^{18}
Input
The input is given from Standard Input in the following format:
N
Output
Print the number of the possible pairs of integers u and v, modulo 10^9+7.
Sample Input 1
3
Sample Output 1
5
The five possible pairs of u and v are:
-
u=0,v=0 (Let a=0,b=0, then 0 xor 0=0, 0+0=0.)
-
u=0,v=2 (Let a=1,b=1, then 1 xor 1=0, 1+1=2.）
-
u=1,v=1 (Let a=1,b=0, then 1 xor 0=1, 1+0=1.）
-
u=2,v=2 (Let a=2,b=0, then 2 xor 0=2, 2+0=2.）
-
u=3,v=3 (Let a=3,b=0, then 3 xor 0=3, 3+0=3.）
Sample Input 2
1422
Sample Output 2
52277
Sample Input 3
1000000000000000000
Sample Output 3
787014179