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
//### In The Name Of GOD ###

//%% Remember; (((He))) is The (((Accepter))) %%

// GOD IS GREATER ...

#include <bits/stdc++.h>

using namespace std;

typedef long long ll ;
typedef long double ld ;

#define int ll
#define pb push_back
#define bp pop_back
#define pf push_front
#define fp pop_front
#define X first
#define Y second
#define IO ios_base::sync_with_stdio(false);
#define sz(a) (int)(a.size())
#define sg(a, b) (a + b - 1) / b

const int MOD = 1000 * 1000 * 1000 + 7;
const int INF = 8 * 1000 * 1000 + 200;
const int MAXN = 4 * 1000 * 100 + 20;
const int MLOG = 18;
const int NMAX = 20;

map<int, int> dp;

int DP(int x){
	if(dp[x]) return dp[x];
	dp[x] = (DP(x / 2) + DP((x - 1) / 2) + DP(x / 2 - 1)) % MOD;
	return dp[x];
}

signed main(){
	IO;
	dp[0] = 1;
	dp[1] = 2;
	int n;
	cin >> n;
	cout << DP(n);
}