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;
#define repp(i,a,b) for(int i = (int)(a) ; i < (int)(b) ; ++i)
#define repm(i,a,b) for(int i = (int)(a) ; i > (int)(b) ; --i)

int main(){
	LL N; cin >> N;
	const LL mod = 1e9+7;
	vector<vector<LL>> dp(2,vector<LL>(2,0));
	dp[0][0] = 1;
	repm(k,59,-1){
		vector<vector<LL>> nx(2,vector<LL>(2,0));
		if(N&(1ll<<k)){
			nx[0][0] = dp[0][0];
			nx[0][1] = (dp[0][0]+dp[0][1])%mod;
			nx[1][0] = (dp[1][0]*2+dp[1][1]+dp[0][0]+dp[0][1])%mod;
			nx[1][1] = (dp[1][0]+dp[1][1]*2+dp[0][1])%mod;
		} else {
			nx[0][0] = (dp[0][0]+dp[0][1])%mod;
			nx[0][1] = dp[0][1];
			nx[1][0] = (dp[1][0]*2+dp[1][1])%mod;
			nx[1][1] = (dp[1][0]+dp[1][1]*2)%mod;
		}
		swap(dp,nx);
	}
	cout << (dp[1][0]+dp[0][0])%mod << endl;
	return 0;
}
