Fox Ciel studies number theory.

She thinks a non-empty set S contains non-negative integers is perfect if and only if for any <image> (a can be equal to b), <image>. Where operation xor means exclusive or operation (http://en.wikipedia.org/wiki/Exclusive_or).

Please calculate the number of perfect sets consisting of integers not greater than k. The answer can be very large, so print it modulo 1000000007 (109 + 7).

Input

The first line contains an integer k (0 ≤ k ≤ 109).

Output

Print a single integer — the number of required sets modulo 1000000007 (109 + 7).

Examples

Input

1


Output

2


Input

2


Output

3


Input

3


Output

5


Input

4


Output

6

Note

In example 1, there are 2 such sets: {0} and {0, 1}. Note that {1} is not a perfect set since 1 xor 1 = 0 and {1} doesn't contain zero.

In example 4, there are 6 such sets: {0}, {0, 1}, {0, 2}, {0, 3}, {0, 4} and {0, 1, 2, 3}.
#include <bits/stdc++.h>
using namespace std;
template <class T>
void debug(T a, T b) {
  ;
}
template <class T>
void chmin(T& a, const T& b) {
  if (a > b) a = b;
}
template <class T>
void chmax(T& a, const T& b) {
  if (a < b) a = b;
}
namespace std {
template <class S, class T>
ostream& operator<<(ostream& out, const pair<S, T>& a) {
  out << '(' << a.first << ',' << a.second << ')';
  return out;
}
}  // namespace std
long long int readL() {
  long long int res;
  scanf("%I64d", &res);
  return res;
}
void printL(long long int res) { printf("%I64d", res); }
const int mod = 1000000007;
struct Int {
  unsigned x;
  int mpow(Int a, int k) {
    Int res = 1;
    while (k) {
      if (k & 1) res = res * a;
      a = a * a;
      k >>= 1;
    }
    return res.x;
  }
  int inverse(Int a) { return mpow(a, mod - 2); }
  Int() : x(0) {}
  Int(long long sig) {
    int sigt = sig % mod;
    if (sigt < 0) sigt += mod;
    x = sigt;
  }
  int get() const { return (int)x; }
  Int& operator+=(Int that) {
    if ((x += that.x) >= mod) x -= mod;
    return *this;
  }
  Int& operator-=(Int that) {
    if ((x += mod - that.x) >= mod) x -= mod;
    return *this;
  }
  Int& operator*=(Int that) {
    x = (unsigned long long)x * that.x % mod;
    return *this;
  }
  Int& operator=(Int that) {
    x = that.x;
    return *this;
  }
  Int& operator/=(Int that) {
    x = (unsigned long long)x * inverse(that.x) % mod;
    return *this;
  }
  Int& operator-() {
    x = mod - x;
    if (x == mod) x = 0;
    return *this;
  }
  bool operator==(Int that) { return x == that.x; }
  bool operator!=(Int that) { return x != that.x; }
  Int operator+(Int that) const { return Int(*this) += that; }
  Int operator-(Int that) const { return Int(*this) -= that; }
  Int operator*(Int that) const { return Int(*this) *= that; }
  Int operator/(Int that) const { return Int(*this) /= that; }
};
namespace std {
ostream& operator<<(ostream& out, const Int& a) {
  out << a.get();
  return out;
}
istream& operator>>(istream& in, Int& a) {
  in >> a.x;
  return in;
}
};  // namespace std
int k;
Int dp[40][40][2];
int main() {
  cin >> k;
  k <<= 1;
  int MX = 31;
  dp[MX][0][0] = 1;
  for (int i = MX; i > 0; --i)
    for (int j = 0; j < (MX + 1); ++j)
      for (int t = 0; t < (2); ++t)
        if (dp[i][j][t] != 0) {
          Int val = dp[i][j][t];
          if (t || k >> i & 1) dp[i - 1][j + 1][t] += val;
          if (j == 0) {
            dp[i - 1][j][t | (k >> i & 1)] += val;
            continue;
          }
          for (int s = 0; s < (2); ++s) {
            if (!t && (k >> i & 1) < s) continue;
            dp[i - 1][j][t | (s < (k >> i & 1))] += val * (1ll << (j - 1));
          }
        }
  Int res = 0;
  for (int i = 0; i < (MX + 1); ++i) {
    res += dp[0][i][0] + dp[0][i][1];
    ;
    ;
  }
  cout << res << endl;
  return 0;
}
