#include <fstream>
using namespace std;

const int mod=666013;

void masol(long long cel[2][2], long long forras[2][2])
{
    for (int i = 0; i < 2; ++i)
        for (int j = 0; j < 2; ++j)
            cel[i][j] = forras[i][j];
}

void szoroz(long long res[2][2], long long bal[2][2], long long jobb[2][2])
{
    for (int i = 0; i < 2; ++i)
        for (int j = 0; j < 2; ++j) {
            res[i][j] = 0;
            for (int k = 0; k < 2; ++k)
                res[i][j] = (res[i][j] + bal[i][k] * jobb[k][j]) % mod;
        }
}


void hatvany(int n, long long a[2][2], long long b[2][2])
{
    if (n == 0)
        return;

    long long aux[2][2];

    if(n%2!=0){
        szoroz(aux, b, a);
        masol(b, aux);
    }

    szoroz(aux, a, a);
    masol(a, aux);
    hatvany(n/2, a, b);
}

long long matyas(int k)
{
    long long a[2][2]={{0,1},{1,1}}, b[2][2]={{1,0},{0,1}};

    if (k == 0) return 0;
    else if (k == 1) return 1;
    hatvany(k-1, a, b);
    return b[1][1]%mod;
}


int main()
{
    /*ofstream fout("output.txt");

    long long a = 0, b = 1, c = 1;
    for (int i = 0; i < 1000000; ++i) {
        // F(i) == a

        long long f = matyas(i);

        if (a == f) {
            //fout << i << " ok\n";
        }
        else {
            fout << i << " " << a << " " << f << "\n";
        }

        a = b;
        b = c;
        c = (a + b) % mod;
    }

    fout << "a tobbi jo\n";*/

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

    int k;
    fin >> k;
    fout << matyas(k) << endl;
}