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 <map>
#include <algorithm>
using namespace std;

map<long long, long long>Map[64];
long long N, mod = 1000000007;

long long solve(int bit, long long rem) {
	if (bit >= 0) rem = min(rem, (4LL << bit) - 2LL);
	if (rem < 0) return 0;
	if (bit == -1) return 1;
	if (Map[bit][rem] >= 1) return Map[bit][rem] - 1;

	long long v1 = solve(bit - 1, rem);
	long long v2 = solve(bit - 1, rem - (1LL << bit));
	long long v3 = solve(bit - 1, rem - (2LL << bit));
	long long D = (v1 + v2 + v3) % mod;
	Map[bit][rem] = D + 1;
	return D;
}

int main() {
	cin >> N;
	cout << solve(60, N) << endl;
	return 0;
}