#include <bits/stdc++.h>
using namespace std;
template <typename T>
bool maxup(T& a, T&& b) {
  if (a < b) {
    a = b;
    return true;
  };
}
template <typename T>
bool maxup(T& a, T& b) {
  if (a < b) {
    a = b;
    return true;
  };
}
template <typename T>
bool minup(T& a, T&& b) {
  if (a > b) {
    a = b;
    return true;
  };
}
template <typename T>
bool minup(T& a, T& b) {
  if (a > b) {
    a = b;
    return true;
  };
}
using VV = vector<vector<long long>>;
using V = vector<long long>;
using P = pair<long long, long long>;
using IP = pair<long long, P>;
template <typename T>
inline void input(vector<T>& v) {
  for (auto& x : v) cin >> x;
}
long long dp[65][3];
signed main() {
  const long long mod = 1e9;
  long long N;
  cin >> N;
  dp[0][0] = 1;
  long long b = log2(N);
  for (long long i = 0; i <= b; i++)
    for (signed j = signed(0); j < signed(3); j++) {
      if (N >> (b - i) & 1) {
        (dp[i + 1][min(j * 2 + 1, 2)] += dp[i][j]) %= mod;
        (dp[i + 1][min(j * 2, 2)] += dp[i][j]) %= mod;
        if (j * 2 - 1 >= 0) (dp[i + 1][min(j * 2 - 1, 2)] += dp[i][j]) %= mod;
      } else {
        (dp[i + 1][min(j * 2, 2)] += dp[i][j]) %= mod;
        if (j * 2 - 1 >= 0) (dp[i + 1][min(j * 2 - 1, 2)] += dp[i][j]) %= mod;
        if (j * 2 - 2 >= 0) (dp[i + 1][min(j * 2 - 2, 2)] += dp[i][j]) %= mod;
      }
    }
  cout << (dp[b + 1][0] + dp[b + 1][1] + dp[b + 1][2]) % mod << endl;
  system("pause");
}
