#include <fstream>
#define MOD 666013

using namespace std;

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

long long k,matrice[2][2]={{0,1},{1,1}},solutie[2][2]={{1,0},{0,1}},a,b,c,d;

void inmultire(long long matrice[][2],long long solutie[][2],long long k)
{
    while(k)
    {
        if(k & 1)
        {
            a=matrice[0][0] * solutie[0][0] + matrice[0][1] * solutie[1][0];
            b=matrice[0][0] * solutie[0][1] + matrice[0][1] * solutie[1][1];
            c=matrice[1][0] * solutie[0][0] + matrice[1][1] * solutie[1][0];
            d=matrice[1][0] * solutie[0][1] + matrice[1][1] * solutie[1][1];
            solutie[0][0]=a % MOD;
            solutie[0][1]=b % MOD;
            solutie[1][0]=c % MOD;
            solutie[1][1]=d % MOD;
            k--;
        }else
        {
            a=matrice[0][0] * matrice[0][0] + matrice[0][1] * matrice[1][0];
            b=matrice[0][0] * matrice[0][1] + matrice[0][1] * matrice[1][1];
            c=matrice[1][0] * matrice[0][0] + matrice[1][1] * matrice[1][0];
            d=matrice[1][0] * matrice[0][1] + matrice[1][1] * matrice[1][1];
            matrice[0][0]=a % MOD;
            matrice[0][1]=b % MOD;
            matrice[1][0]=c % MOD;
            matrice[1][1]=d % MOD;
            k>>=1;
        }
    }
}

int main()
{
    in>>k;
    inmultire(matrice,solutie,k-1);
    out<<solutie[1][1];
    in.close();
    out.close();
    return 0;
}

//Varianta de 20p

/*#include <fstream>

using namespace std;

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

int prod[3][3];

int main()
{
    int i,k,a,b,c,d,p,l;
    prod[1][1]=0;
    prod[1][2]=1;
    prod[2][1]=1;
    prod[2][2]=1;
    //fibonaci[1]=0;
    //fibonaci[2]=1;

    in>>k;

    for(i=1;i<k-1;i++)
    {
        a=prod[1][1] % 666013;
        b=prod[1][2] % 666013;
        c=prod[2][1] % 666013;
        d=prod[2][2] % 666013;
        prod[1][1]=(a*0+b*1) % 666013;
        prod[1][2]=(a*1+b*1) % 666013;
        prod[2][1]=(c*0+d*1) % 666013;
        prod[2][2]=(c*1+d*1) % 666013;
        //out<<prod[1][1]<<" "<<prod[1][2]<<"\n";
        //out<<prod[2][1]<<" "<<prod[2][2]<<"\n";
        //out<<"Apoi"<<"\n";
    }
    out<<prod[2][2] % 666013;
    in.close();
    out.close();
    return 0;
}
*/