#include <iostream>
#include <vector>
using namespace std;
// (1+sqrt(3)) ^ n + (1 - sqrt(3)) ^ nは次のような数列になる
// 2, 2, 8, 20, 56, 152, ... f(n+2)=2(f(n + 1) + f(n))
// (1 - sqrt(3)) ^ n < 1より上の数列の値-1が求める整数
// 
const int64_t MOD = 1000;
void next(vector<long> &x, const vector<long> &first, long MOD) {
  long last = x.back();
  for(int i = x.size() - 2;  i >= 0 ; i--) x[i + 1] = x[i];
  x[0] = 0;
  for(int i = 0; i < x.size(); i++) x[i] = (MOD + x[i] - (long)last * first[i] % MOD) % MOD;
}

vector<long> next2N(const vector<long> &x, const vector<long> &first, long MOD) {
  vector<long> tmp(x);
  vector<long> result(x.size());
  for(int i = 0; i < x.size(); i++) {
    for(int j = 0; j < tmp.size(); j++) {
      result[j] = (result[j] + MOD - x[i] * tmp[j]) % MOD;
    }
    next(tmp, first, MOD);
  }
  return result;
}
long calc(const vector<long> &poly, const vector<long> &x, long MOD, int ofs = 0) {
  __int128_t ret = 0;
  for(int i = 0; i < poly.size(); i++) {
    ret += x[i + ofs] * poly[i] % MOD;
    ret %= MOD;
  }
  return (MOD - ret) % MOD;
}
long kitamasa(const vector<long> &poly, const vector<long> &x, int64_t N, long MOD) {
  if(N < poly.size()) return x[N];
  int t = poly.size(), l = 0;
  while(t > 0) t >>= 1, l++;
  for(int i = 0; i <= l; i++) {
    if(N >> (63 - __builtin_clzl(N) - l + i) & 1) {
      t |= 1LL << i;
    }
  }
  long cur = poly.size();
  vector<long> curPoly = poly;
  vector<long> poy2 = poly;
  while(cur < t) {
    if(cur == N) {
      return calc(curPoly, x, MOD);
    }
    next(curPoly, poly, MOD);
    cur++;
  }
  vector<long> ret(curPoly.size());
  cur = 0;
  for(int i = 63 - __builtin_clzl(N) - l - 1; i >= 0; i--) {
    curPoly = next2N(curPoly, poly, MOD);
    if(N >> i & 1) next(curPoly, poly, MOD);
  }
  return calc(curPoly, x, MOD);
}

int main() {
  int n;
  cin >> n;
  vector<int64_t> poly(2, -2);
  vector<int64_t> iv(2, 2);
  cout << (kitamasa(poly, iv, n, MOD) + MOD - 1) % MOD << endl;
}