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 mod = 1e9+7;

#define REP(i, n) for (int (i) = 0; (i) < (n); ++(i))

int f[65][2][2][2], a[65], sz = 62;

void add(int &x, int y) {
	x += y;
	if (x >= mod) x -= mod;
}

int calc(long long n) {
	memset(f, 0, sizeof f);
	REP(i, sz) a[i] = n % 2, n /= 2;
	reverse(a, a + sz);
	f[0][0][0][0] = 1;
	REP(i, sz) REP(x, 2) REP(y, 2) REP(z, 2) if (f[i][x][y][z]) {
		int bit = a[i];
		REP(a, 2) REP(b, a+1) REP(c, 2) {
			int val1 = a^b^c;
			int val2 = a^b;
			int shift = (a+b+c)/2;
			if (shift ^ z) continue;
			if (!x && val1 > bit) continue;
			if (!y && val2 > bit) continue;
			add(f[i+1][x|(val1<bit)][y|(val2<bit)][c], f[i][x][y][z]);
		}
	}
	int result = 0;
	REP(x, 2) REP(y, 2) add(result, f[sz][x][y][0]);
	return result;
}

int main() {
	long long n;
	cin >> n;
	cout << calc(n) << endl;
	return 0;
}