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;

long long N;
const int md = 1e9 + 7;
const int a[] = {0, 0, 1};
const int b[] = {1, 0, 1};

int f[64][3];

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> N;
	f[63][0] = 1;
	for (int i = 62; i >= 0; --i) {
		int x = (N >> i & 1);
		for (int j = 0; j <= 2; ++j) {
			if (!f[i+1][j]) continue;
			for (int k = 0; k < 3; ++k) {
				int nj = j * 2 + x - (a[k] + b[k]);
				if (nj < 0) continue;
				nj = min(nj, 2);
				f[i][nj] = (f[i][nj] + f[i+1][j]) % md;
			}
		}
	}

	int ans = 0;
	for (int i = 0; i <= 2; ++i) ans = (ans + f[0][i]) % md;
	cout << ans << endl;
}