#include <stdio.h>

const long long int MOD = 666013;

class Mat2
{
public:
    Mat2(long long int a, long long int b, long long int c, long long int d)
    {
        m_mat[0][0] = a;
        m_mat[0][1] = b;
        m_mat[1][0] = c;
        m_mat[1][1] = d;
    }

    long long int& a(){ return m_mat[0][0]; }
    long long int& b(){ return m_mat[0][1]; }
    long long int& c(){ return m_mat[1][0]; }
    long long int& d(){ return m_mat[1][1]; }

    Mat2 operator*(const Mat2& a)
    {
        return Mat2(
                ((m_mat[0][0] * a.m_mat[0][0]) % MOD + m_mat[0][1] * a.m_mat[1][0]) % MOD,
                ((m_mat[0][0] * a.m_mat[1][0]) % MOD + m_mat[0][1] * a.m_mat[1][1]) % MOD,
                ((m_mat[1][0] * a.m_mat[0][0]) % MOD + m_mat[1][1] * a.m_mat[1][0]) % MOD,
                ((m_mat[1][0] * a.m_mat[1][0]) % MOD + m_mat[1][1] * a.m_mat[1][1]) % MOD
        );
    }

private:
    long long int m_mat[2][2];
};

Mat2 logput(Mat2 a, int b, int mod)
{
    if(b == 1)
        return a;

    Mat2 x = logput(a, b/2, mod);
    x = x * x;

    if(b % 2)
        x = x * a;

    return x;
}

int main()
{
    FILE *fin = fopen("kfib.in", "r"),
         *fout = fopen("kfib.out", "w");
    int n;
    Mat2 f(0, 1, 1, 1);

    fscanf(fin, "%d", &n);
    f = logput(f, n, MOD);
    fprintf(fout, "%lld", f.b());

    fcloseall();
    return 0;
}