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
#include<iostream>
#include<map>

using namespace std;

typedef long long llint;

const int MOD = 1000000007;

llint n;
llint sol[75];
map <llint, llint> bio;

llint add (llint a, llint b) {
	if (a+b>=MOD) return a+b-MOD; return a+b;
}

llint sub (llint a, llint b) {
	if (a-b<0) return a-b+MOD; return a-b;
}

llint mul (llint a, llint b) {
	return (a*b)%MOD;
}

llint f (llint x) {
	if (x==0) return 0;
	if (bio[x]) return bio[x];
	llint pot=1, cnt=0, res=0;
	while (pot*2<=x) pot*=2, cnt++;
	if (pot==x) {
		return sol[cnt];
	} else {
		res=sub(mul(2, sol[cnt]), 1);
		res=sub(res, f(sub(sub(pot, sub(x, pot)), 1)));
		res=add(res, f(x-pot));
		bio[x]=res;
		return res;
	}
}

int main () {
	cin >> n;
	sol[0]=1;
	for (int i=1; i<70; i++) {
		sol[i]=sub(mul(sol[i-1], 3), 1);
	}
	cout << f(n+1);
	return 0;
}



