#include <stdio.h>
#include <bits/stdc++.h>

#define rep(i, n) for(int i = 0; i < n; i++)
#define repa(i, l, r) for (int i = l; i < r; i++)
#define repd(i, r, l) for (int i = r; i > l; i--)

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
const int mod = 666013;
ifstream fin ("kfib.in");
ofstream fout ("kfib.out");

void square(ll a[2][2]) {
  ll z[2][2] = {
    {
      ((a[0][0]*a[0][0] + a[0][1]*a[1][0]) % mod),
      ((a[0][0]*a[0][1] + a[0][1]*a[1][1]) % mod)
    },
    {
      ((a[1][0]*a[0][0] + a[1][1]*a[1][0]) % mod),
      ((a[1][0]*a[0][1] + a[1][1]*a[1][1]) % mod)
    }
  };
  rep(i,2)
  rep(j,2)
    a[i][j] = z[i][j];
}

void mult(ll x[2][2], ll a[2][2]) {
  ll z[2][2] = {
    {
      ((x[0][0]*a[0][0] + x[0][1]*a[1][0]) % mod),
      ((x[0][0]*a[0][1] + x[0][1]*a[1][1]) % mod)
    },
    {
      ((x[1][0]*a[0][0] + x[1][1]*a[1][0]) % mod),
      ((x[1][0]*a[0][1] + x[1][1]*a[1][1]) % mod)
    }
  };
  rep(i,2)
  rep(j,2)
    x[i][j] = z[i][j];
}

int n;
int main(void) {
  fin >> n;

  ll x[2][2] = {{1,0},{0,1}};
  ll a[2][2] = {{1,1},{1,0}};
  while(n) {
    if (n&1) {
      mult(x, a);
    }
    n /= 2;
    square(a);
  }

  fout << x[0][1] << endl;
  return 0;
}