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;
#define REP(i, n) for (int i = 0; i < int(n); ++i)
#define REPE(i, a, b) for (int i = (a); i <= int(b); ++i)
using LL = long long;

const LL mod = 1e9 + 7;

map<LL, LL> d;

LL f(LL x) {
  if (x <= 1) return x;
  if (d.count(x)) return d[x];
  LL y = (x - 1) / 2;
  LL a = f(y);
  LL b = f(y + 1);
  LL ret;
  if (x & 1) {
    ret = (a * 3 + (b - a)) % mod;
    if (ret < 0) ret += mod;
  } else {
    ret = (a * 3 + (b - a) * 2) % mod;
    if (ret < 0) ret += mod;
  }
  return d[x] = ret;
}

int main() {
  LL n;
  cin >> n;
  cout << f(n + 1) << endl;
  return 0;
}

