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<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD=1e9+7;
ll n;
ll f[62][2][2];
ll dp(int i, int mod , bool ok)
{
	ll& ans=f[i][mod][ok];
	if(ans!=-1)return ans;
	if(i==60)return ans=(mod==0 and ok==0);
	int nthbit=(n>>i)&1;
	ans=0;
	for(int a=0;a<2;a++)
	{
		for(int b=0;b<=a;b++)
		{
			int curbit=(a+b+mod)%2;
			int nmod=(a+b+mod)/2;
			bool nok=ok;
			if(curbit>nthbit)nok=1;
			if(curbit<nthbit)nok=0;
			ans+=dp(i+1, nmod, nok);
			ans=ans%MOD;
		}
	}
	return ans;
}
int main()
{
	cin>>n;
	memset(f, -1, sizeof f);
	cout<<dp(0,0,0);
	
	
	
}