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

typedef long long ll;
typedef pair<int, int> ii;

const int mod = 1e9 + 7; 

int dp[60][2][2]; 
long long N;

int f(int i, int c, int ok) {
  if(i == 60) return !c && ok; 
  int &ret = dp[i][c][ok];
  if(~ret) return ret; 
  ret = 0; 
  
  int nbit = N >> i & 1;
  for(int a = 0; a <= 1; ++a) {
    for(int b = 0; b <= a; ++b) {
      int bit = a ^ b ^ c; 
      int carry = a + b + c >> 1; 
      int nok = bit == nbit ? ok : bit > nbit ? 0 : 1; 
      ret += f(i + 1, carry, nok); 
      if(ret >= mod) ret -= mod; 
    }
  }

  return ret; 
}

int main() {
  scanf("%lld", &N); 
  memset(dp, -1, sizeof dp); 
  printf("%d\n", f(0, 0, 1));   
}
