#include <bits/stdc++.h>

using namespace std;

ifstream fin("kfib.in");
ofstream fout("kfib.out");

struct Matrix{
    long long v[3][3];

    Matrix(int a, int b, int c, int d)
    {
        v[1][1] = a;
        v[1][2] = b;
        v[2][1] = c;
        v[2][2] = d;
    }

    Matrix operator * (const Matrix& A)
    {
        Matrix rez(0, 0, 0, 0);

        for(int i = 1; i <= 2; ++i)
            for(int j = 1; j <= 2; ++j)
                for(int k = 1; k <= 2; ++k)
                    rez.v[i][j] = (rez.v[i][j] + 1LL*v[i][k]*A.v[k][j]%666013) %  666013;

        return rez;
    }

    Matrix operator ^ (int N)
    {
        if(N == 0)
            return Matrix(1, 0, 0, 1);

        if(N == 1)
            return *this;

        Matrix X = *this ^ (N/2);

        X = X * X;

        if(N & 1) X = X * *this;

        return X;
    }
};


int main()
{
    int N;

    fin >> N;

    if(N == 0)
        fout << 0;
    else if(N == 1)
        fout << 1;
    else{
        Matrix A(1, 1, 1, 0);

        A = A ^ (N - 1);

        fout << A.v[1][1];
    }
}