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<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> bi;
vector<vector<int>> dp;
ll def;
ll rec(int i,int j){

	ll ans=0;
	if(i==-1){
		return 1;
	}
	if(dp[i][j])return dp[i][j];
	if(j==0){
		if(bi[i]){
			ans+=rec(i-1,0)+rec(i-1,1);
		}else{
			ans+=rec(i-1,0);
		}
	}else if(j==1){
		if(bi[i]){
			ans+=rec(i-1,1)+2*rec(i-1,2);
		}else{
			ans+=rec(i-1,0)+rec(i-1,1)+rec(i-1,2);
		}
	}else{
		ans+=3*rec(i-1,2);
	}
	ans%=def;
//	cout<<i<<' '<<j<<' '<<ans<<endl;
	dp[i][j]=ans;
	return ans;
}
int main() {
	ll n;cin>>n;
	while(n){
		bi.push_back(n%2);
		n/=2;
	}
//	reverse(bi.begin(),bi.end());
	def=1;
	for(int i=0;i<9;i++)def*=10;
	def+=7;
	dp=vector<vector<int>>(bi.size(),vector<int>(3,0));
//	dp[bi.size()-1][0];
//	for(int i=bi.size()-2;i>=0;i--){
//
//	}

	ll ans=rec(bi.size()-1,0);
	ans%=def;
	cout<<ans<<endl;
	return 0;
}
