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.

Examples

Input

3


Output

5


Input

1422


Output

52277


Input

1000000000000000000


Output

787014179
//Prefix sum of OEIS A002487
//a(0)=0, a(1)=1; a(2n) = a(n), a(2n+1) = a(n) + a(n+1)
//s(2*n+1) = 3*s(n) + a(n+1)
#include<bits/stdc++.h>
using namespace std;
#define i128 __int128_t
#define i64 long long int
map<i128,i128> A;
i128 a(i128 x){
	if(x <= 1)return x;
	if(A.count(x))return A[x];
	if(x%2==0)return a(x/2);
	return A[x] = a(x/2)+a(x/2+1);
}
i128 s(i128 x){
	if(x <= 1)return x;
	if(x%2==0)return s(x+1)-a(x+1);
	return 3*s(x/2)+a(x/2+1);
}
int main(){
	i64 n;
	cin >> n;
	cout << (int)(s((i128)(n+1)) % 1000000007) << endl;
	return 0;
}
