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


typedef long long ll;
ll MOD = 1000000007;
ll N;
//-----------------------------------------------------------------
ll solve(ll n) {
	set<int> cnt;
	rep(i, 0, n + 1) {
		int j = n - i;
		if (i > j) break;
		cnt.insert(i^j);
	}

	return cnt.size();
}

map<ll, ll> memo;
ll a(ll n) {
	if (0 < memo[n]) return memo[n];

	if (n < 2) {
		if (n < 1)
			return memo[n] = 1;
		else
			return memo[n] = 3;
	} else {
		if (n % 2 == 0) {
			if (n == 2)
				return memo[n] = 4;
			else
				return memo[n] = (a(n / 2 - 2) + 2 * a(n / 2 - 1) + 2) % MOD;
		}
		else {
			return memo[n] = (2 * a((n - 3) / 2) + a((n - 1) / 2) + 2) % MOD;
		}
	}
}

int main() {
	cin >> N;
	cout << (a(N - 1) + 1) % MOD << endl;
}