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>
#define Rint register int
#define MP make_pair
using namespace std;
typedef long long LL;
typedef pair<LL, LL> pii;
const int mod = 1e9 + 7;
LL n;
map<pii, int> M;
inline void upd(int &a, int b){a += b; if(a >= mod) a -= mod;}
inline int dfs(LL x, LL y){
	if(y < 0) return 0;
	if(!y) return 1;
	if(M.count(MP(x, y))) return M[MP(x, y)];
	int res = dfs(x >> 1, y >> 1);
	upd(res, dfs(x - 1 >> 1, y - 1 >> 1));
	if(y >= 2) upd(res, dfs(x >> 1, y - 2 >> 1));
	return M[MP(x, y)] = res;
}
int main(){
	scanf("%lld", &n);
	printf("%d", dfs(n, n));
}