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 mod 1000000007
using namespace std;

long long n;
int len,a[105],dp[105][2][2][2][2];
int main(){
	scanf("%lld",&n); n++;
	int i,j,k,x,y,u,v,t1,t2,p,q;
	for (; n; n>>=1) a[++len]=n&1;
	dp[0][1][1][0][1]=1;
	//第i为，与n关系为j,k，有无a+b=v+1<<i，有无a+b=v
	for (i=1; i<=len; i++)
		for (j=0; j<2; j++)
			for (k=0; k<2; k++)
				for (x=0; x<2; x++)
					for (y=0; y<2; y++) if (x+y>0)
						for (u=0; u<=((j)?1:a[i]); u++)
							for (v=0; v<=((k)?1:a[i]); v++){
								t1=t2=0;
								for (p=0; p<2; p++)
									for (q=0; q<2; q++){
										if ((p^q)==u && (x && p+q+1==v+2 || y && p+q==v+2)) t1=1;
										if ((p^q)==u && (x && p+q+1==v || y && p+q==v)) t2=1;
									}
								dp[i][j][k][t1][t2]=(dp[i][j][k][t1][t2]+dp[i-1][j|(u<a[i])][k|(v<a[i])][x][y])%mod;
							}
	printf("%d\n",(dp[len][0][0][0][1]+dp[len][0][0][1][1])%mod);
	return 0;
}
