#include <iostream>
#include <fstream>
using namespace std;
ifstream f1("kfib.in");
ofstream f2("kfib.out");
#define BASE 666013

struct Matrice
{
    Matrice() {}

    Matrice(int a1, int a2, int b1, int b2)
    {
        data[0][0]= a1;
        data[0][1]= a2;
        data[1][0]= b1;
        data[1][1]= b2;
    }

    long long data[2][2];
};

Matrice operator*(Matrice m1, Matrice m2)
{
    Matrice rez(0,0,0,0);

    for (int i=0; i<2; i++)
        for (int j=0; j<2; j++)
            for (int k=0; k<2; k++)
            {
                rez.data[i][j]+= m1.data[i][k]*m2.data[k][j];
                rez.data[i][j]%= BASE;
            }

    return rez;
}

Matrice power(Matrice m, int p)
{
    if (p == 1)
        return m;

    Matrice rez = power(m, p/2);
    rez= rez*rez;

    if (p % 2 != 0)
        rez= rez * m;

    return rez;
}

int kfibmodulo(int k)
{
    int f0 = 0, f1 = 1;

    Matrice m0 = Matrice(0,1,1,1);
    Matrice m = power(m0,k-1);
    Matrice rez = Matrice(f0,f1,0,0) * m;

    return rez.data[0][1];
}

int main()
{
    int k;

    f1 >> k;
    f2 << kfibmodulo(k);

    f2.close();
    return 0;
}