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
n=int(input())
mod=10**9+7
bt=bin(n)[2:]
k=len(bt)
dp=[[0]*2 for i in range(k+1)]
dp[0][0]=1
dp[0][1]=1
for i in range(k):
  j=int(bt[k-i-1])
  a,b,c=[(1,0,0),(1,1,0)][j]
  d,e,f=[(1,1,1),(0,1,2)][j]
  dp[i+1][0]=(a*dp[i][0]+b*dp[i][1]+c*(3**i))%mod
  dp[i+1][1]=(d*dp[i][0]+e*dp[i][1]+f*(3**i))%mod
print(dp[k][0])