#include <bits/stdc++.h>
#define int int64_t

using namespace std;

const int kMod = 666013;

int modulo (int a, int b=kMod) { return a >= 0 ? a % b : ( b - abs ( a%b ) ) % b; }

struct ModInt {
  long long n;
  
  ModInt(long long n = 0) : n(n % kMod) {}
  ModInt operator+(const ModInt& oth) { return n + oth.n; }
  ModInt operator-(const ModInt& oth) { return n - oth.n; }
  ModInt operator*(const ModInt& oth) { return n * oth.n; }
  long long get() { return n < 0 ? n + kMod : n; }
};

ModInt lgpow(ModInt b, int e) {
  ModInt r;
  for (r = 1; e; e /= 2, b = b * b)
    if (e % 2) r = r * b;
  return r;
}
ModInt inv(ModInt x) { return lgpow(x, kMod - 2); }

vector<ModInt> BerlekampMassey(vector<ModInt> s) {
  int n = s.size();
  vector<ModInt> C(n, 0), B(n, 0);
  C[0] = B[0] = 1;
  
  ModInt b = 1; int L = 0;
  for (int i = 0, m = 1; i < n; ++i) {
    /// Calculate discrepancy
    ModInt d = s[i];
    for (int j = 1; j <= L; ++j)
      d = d + C[j] * s[i - j];
    
    if (d.get() == 0) { ++m; continue; }
    
    /// C -= d / b * B * x^m
    auto T = C; ModInt coef = d * inv(b);
    for (int j = m; j < n; ++j)
      C[j] = C[j] - coef * B[j - m];
    
    if (2 * L > i) { ++m; continue; }
    
    L = i + 1 - L; B = T; b = d; m = 1;
  }
  
  C.resize(L + 1); C.erase(C.begin());
  for (auto& x : C) x = ModInt(0) - x;
  
  return C;
}

template<typename T>
struct LinearRec {
  using Poly = vector<T>;
  int n; Poly first, trans;
  
  // Recurrence is S[i] = sum(S[i-j-1] * trans[j])
  // with S[0..(n-1)] = first
  LinearRec(const Poly &first, const Poly &trans) :
    n(first.size()), first(first), trans(trans) {}
  
  Poly combine(Poly a, Poly b) {
    Poly res(n * 2 + 1, 0);
    // You can apply constant optimization here to get a
    // ~10x speedup
    for (int i = 0; i <= n; ++i)
      for (int j = 0; j <= n; ++j)
        res[i + j] = res[i + j] + a[i] * b[j];
    
    for (int i = 2 * n; i > n; --i)
      for (int j = 0; j < n; ++j)
        res[i - 1 - j] = res[i - 1 - j] + res[i] * trans[j];
    
    res.resize(n + 1);
    return res;
  }
  
  // Consider caching the powers for multiple queries
  T Get(int k) {
    Poly r(n + 1, 0), b(r);
    r[0] = 1; b[1] = 1;
    
    for (++k; k; k /= 2) {
      if (k % 2)
        r = combine(r, b);
      b = combine(b, b);
    }
    
    T res = 0;
    for (int i = 0; i < n; ++i)
      res = res + r[i + 1] * first[i];
    return res;
  }
};

vector<ModInt> Fib={0,1,1};

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    auto res=BerlekampMassey(Fib);
    int k;
    cin>>k;
    auto x=LinearRec<ModInt>({0,1},res).Get(k);
    cout<<x.get();
    return 0;
}