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;

typedef pair<int, int> pii;
typedef long long ll;
typedef vector<int> vi;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define ALL(c) (c).begin(),(c).end()

const ll MOD = 1000000007;

ll dp[60][3];
bool p[60];

inline void add(ll &x, ll y)
{
	x += y;
	if (x >= MOD) x -= MOD;
}

int main() {
	ll N;
	cin >> N;
	rep(i, 60) p[59-i] = (N >> i) & 1;

	dp[0][0] = 1;

	rep(i, 60) {
		rep(j, 3) {
			add(dp[i+1][2], dp[i][2]);
		}

		rep(j, 2) if (dp[i][j] > 0) {
			rep(k, 3) {
				int nj = min(j * 2 + p[i] - k, 2);
				if (nj < 0) continue;
				add(dp[i+1][nj], dp[i][j]);
			}
		}
	}

	cout << (dp[60][0] + dp[60][1] + dp[60][2]) % MOD << endl;

	return 0;
}