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 ll long long
#define pb push_back
#define mk make_pair
#define rint register int
using namespace std;
const int mod = 1e9+7;
inline int read(){int w=1,s=0;char ch=getchar();while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}while(isdigit(ch)){s=s*10+ch-'0';ch=getchar();}return w*s;}
ll n;
typedef pair<int,int> pa;
map<pa,int> mp;
inline int add(int a,int b){a+=b;if(a>=mod) a-=mod;return a;}
inline int DFS(ll a,ll b){
	if(b<0) return 0;
	if(b==0) return 1;
	if(mp.count(mk(a,b))) return mp[mk(a,b)];
	int res=0;
	res=add(res,DFS(a>>1,b>>1));
	res=add(res,DFS((a-1)>>1,(b-1)>>1));
	if(b>=2) res=add(res,DFS(a>>1,(b-2)>>1));
	return mp[mk(a,b)]=res;
}
int main()
{
	cin>>n;
	cout<<DFS(n,n);
	return 0;
}