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>
#define ll long long
using namespace std;

ll mod=1000000007, beki3[80], ans=0;
map<ll, ll> mp;

void solve(){
	auto itr=mp.end();
	--itr;
	ll n=itr->first, m=itr->second;
	if(n==0) ans=(ans+m)%mod;
	else if(n>0){
		int d=61;
		while(!(n&((ll) 1<<d))) --d;
		ll x=((ll) 1<<d);
		ans=(ans+(beki3[d]*m)%mod)%mod;
		mp[n-x]=(mp[n-x]+m)%mod;
		mp[x*2-n-3]=(mp[x*2-n-3]+mod-m)%mod;
	}
	mp.erase(itr);
}

int main() {
	ll N;
	cin >> N;
	beki3[0]=1;
	for(int i=1; i<80; ++i) beki3[i]=(beki3[i-1]*3)%mod;
	mp[N]=1;
	while(mp.size()>0) solve();
	cout << ans << endl;
	return 0;
}