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 INF (1<<30)
#define INFLL (1ll<<60)
typedef pair<int, int> P;
typedef pair<int, P> E;
#define MOD (1000000007ll)
#define l_ength size

void mul_mod(ll& a, ll b){
	a *= b;
	a %= MOD;
}

void add_mod(ll& a, ll b){
	b += MOD;
	a += b;
	a %= MOD;
}

ll dp[62][3];

int main(void){
	ll n;
	int i,j,v,d;
	fill(dp[0],dp[62],0ll);
	dp[61][0] = 1ll;
	cin >> n;
	for(i=60; i>=0; --i){
		for(j=0; j<3; ++j){
			v = ((n >> i) % 2) + j * 2;
			for(d=0; d<3; ++d){
				if(v<d){
					continue;
				}
				add_mod(dp[i][min(v-d,2)],dp[i+1][j]);
			}
		}
	}
	cout << ((dp[0][0]+dp[0][1]+dp[0][2])%MOD) << endl;
	return 0;
}
