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<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int mod=1000000007;
int dp[2][2][2];
int main()
{
	long long n;
	int now=0,to=1,nv,rv,h;
	scanf("%lld",&n);
	memset(dp,0,sizeof(dp));
	dp[now][0][0]=1;
	for(int i=0;i<=59;i++)
	{
		for(int j=0;j<2;j++)
			for(int k=0;k<2;k++)
				if(dp[now][j][k])
				{
					nv=((n>>i)&1);
					for(int z=0;z<3;z++)
					{
						rv=((z+k)&1);
						h=(z+k)>>1;
						if(rv<nv)
							(dp[to][0][h]+=dp[now][j][k])%=mod;
						else if(rv==nv)
							(dp[to][j][h]+=dp[now][j][k])%=mod;
						else if(rv>nv)
							(dp[to][1][h]+=dp[now][j][k])%=mod;
					}
					dp[now][j][k]=0;
				}
		swap(now,to);
	}
	printf("%d",dp[now][0][0]);
	return 0;
}