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;
const int mod = 1e9 + 7;
long long two[35];
int f[35][35][2], d[35];
int n, len;
int add(int a, int b) { return a + b >= mod ? a + b - mod : a + b; }
int dfs(int i, int j, int limit) {
  if (!i) return 1;
  if (f[i][j][limit] != -1) return f[i][j][limit];
  int res = 0;
  if (!limit) {
    res = add(res, two[j] * dfs(i - 1, j, 0) % mod);
    res = add(res, dfs(i - 1, j + 1, 0));
  } else {
    res = add(res, two[j == 0 ? 0 : j - 1] * dfs(i - 1, j, d[i] == 0) % mod);
    if (d[i]) {
      res = add(res, (j == 0 ? 0 : two[j - 1]) * dfs(i - 1, j, 1) % mod);
      res = add(res, dfs(i - 1, j + 1, 1));
    }
  }
  f[i][j][limit] = res;
  return res;
}
int main() {
  two[0] = 1;
  for (int i = 1; i < 32; i++) two[i] = add(two[i - 1], two[i - 1]);
  scanf("%d", &n);
  while (n) {
    d[++len] = n & 1;
    n >>= 1;
  }
  memset(f, -1, sizeof(f));
  printf("%d\n", dfs(len, 0, 1));
  return 0;
}
