#include <bits/stdc++.h>

using namespace std;

const int MOD = 666013;

class Matrix {
  public:
    static const int DIM = 2;
    int mat[DIM][DIM];
    Matrix (int num = 0) {
      mat[0][1] = mat[1][0] = 0;
      mat[0][0] = mat[1][1] = num;
    }
    Matrix operator * (const Matrix& other) const {
      Matrix ans;
      for (int i = 0; i < DIM; ++i)
        for (int j = 0; j < DIM; ++j)
          for (int k = 0; k < DIM; ++k)
            ans.mat[i][j] = (ans.mat[i][j] + 1LL * mat[i][k] * other.mat[k][j]) % MOD;
      return ans;
    }
};

int main()
{
    int n;
    ifstream fin("kfib.in");
    fin >> n;
    fin.close();
    Matrix base, ans(1);
    base.mat[0][1] = base.mat[1][0] = base.mat[1][1] = 1;
    for (int expo = n - 1; expo > 0; expo >>= 1, base = base * base)
      if (expo & 1)
        ans = ans * base;
    ofstream fout("kfib.out");
    fout << ans.mat[1][1] << '\n';
    fout.close();
    return 0;
}