#include<stdio.h>
#include<iostream>
#include<vector>
#define MOD 666013
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<long long> vll;
typedef vector<vector<int> > vvi;
typedef vector<vll> vvll;
typedef vector<pair<int, int> > vpi;

#define sz(c) (int)(c).size()
#define pb push_back
#define mp make_pair
#define fs first
#define sc second

int N;
vvll v;

vvll mul(vvll &a, vvll &b) {
  int N = sz(a), M = sz(a[0]), P = sz(b[0]);
  vvll ret(N, vll (P,0));
  for(int i=0;i<N;++i) {
    for(int j=0;j<P;++j) {
      for(int k=0;k<M;++k) {
        ret[i][j] += a[i][k]*b[k][j];
        ret[i][j] %= MOD;
      }
    }
  }
  return ret;
}

vvll matpw(vvll &v, long long k) {
  int N = sz(v);
  vvll ret(N, vll(N,0));
  for(int i=0;i<N;++i) ret[i][i] = 1;
  for(int i=0;(1LL<<i) <= k; ++i) {
    if( (1LL<<i) & k) {
      ret = mul(ret, v);
    }
    v = mul(v,v);
  }
  return ret;
}

int main() {
  freopen("kfib.in","r",stdin);
  freopen("kfib.out","w",stdout);
  scanf("%d",&N);
  if(N==0) {
    printf("%d",0);
    return 0;
  }
  v.resize(2, vll(2,1));
  v[0][0] = 0;

  v = matpw(v, N);
  printf("%lld",v[0][1]);
}