#include <bits/stdc++.h>
using namespace std;
const long long DDD = (1e9) + 9;
map<pair<long long, long long>, long long> dp;
long long func(long long S, long long X) {
  if (S < 0 || X < 0) return 0;
  if (S == 0 && X == 0) return 1;
  pair<long long, long long> key = make_pair(S, X);
  if (dp.find(key) != dp.end()) {
    return dp[key];
  }
  dp[key] =
      (func(S / 2, X / 2) +
       func((long long)floor((S - 1) / 2.0), (long long)floor((X - 1) / 2.0)) +
       func((long long)floor((S - 2) / 2.0), (long long)floor((X) / 2.0))) %
      DDD;
  return dp[key];
}
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  long long N;
  cin >> N;
  cout << func(N, N) << endl;
  return 0;
}
