#include <fstream>

using namespace std;

ifstream f("kfib.in");
ofstream g("kfib.out");

const int M = 666013;

long long p[3][3], m1[3][3], m[3][3];

void scrie(long long a[3][3])
{
    g << a[1][1] << "\t" << a[1][2] << "\n";
    g << a[2][1] << "\t" << a[2][2] << "\n\n";
}

void inmulteste (long long a[3][3], long long b[3][3])
{
    m[1][1] = (((a[1][1] * b[1][1]) % M) + ((a[1][2] * b[2][1]) % M)) % M;
    m[1][2] = (((a[1][1] * b[1][2]) % M) + ((a[1][2] * b[2][2]) % M)) % M;
    m[2][1] = (((a[2][1] * b[1][1]) % M) + ((a[2][2] * b[2][1]) % M)) % M;
    m[2][2] = (((a[2][1] * b[1][2]) % M) + ((a[2][2] * b[2][2]) % M)) % M;

    /*g << "inmultesc:\n";
    scrie(a);
    g << "\ncu:\n";
    scrie(b);
    */

    a[1][1] = m[1][1];
    a[1][2] = m[1][2];
    a[2][1] = m[2][1];
    a[2][2] = m[2][2];

    /*g << "\nsi obtin:\n";
    scrie(a);
    */
}

int main()
{
    int k;

    f >> k;

    m1[1][2] = 1; m1[2][1] = 1; m1[2][2] = 1;

    p[1][1] = p[2][2] = 1;

    k--;

    while(k > 0)
    {
        if (k % 2 != 0)
            inmulteste(p, m1);
        k /= 2;
        inmulteste(m1, m1);
    }
    //scrie(p);
    g << p[2][2];

    return 0;
}