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;

const int LOG = 60;
const int MOD = 1e9 + 7;

long long n;
map<pair<int, long long>, int> f;

int power(int a, int n) {
	int ret = 1;
	for (int i = 1; i <= n; i++) {
		ret = 1LL * ret * a % MOD;
	}
	return ret;
}

int dfs(int i, long long n) {
	if (i == -1) {
		return 1;
	}
	if (f.count({i, n})) {
		return f[{i, n}];
	}
	if ((1LL << (i + 2)) - 1 <= n) {
		return power(3, i + 1);
	}
	int &ret = f[{i, n}];
	ret = 0;
	for (long long v = 0; v < 2; v++) {
		if ((v << i) > n) continue;
		ret += dfs(i - 1, n - (v << i));
		ret %= MOD;
		if (v == 0 && (1LL << (i + 1)) <= n) {
			ret += dfs(i - 1, n - (1LL << (i + 1)));
			ret %= MOD;
		}
	}
	return ret;
}

int main() {
	cin >> n;
	cout << dfs(LOG, n) << endl;
	return 0;
}
