#include <iostream>

#define mod 666013

#include <fstream>

using namespace std;



ifstream f("kfib.in");

ofstream g("kfib.out");



class matrice{



private:

    long long s1,s2,j1,j2,k_term;



public:

    matrice(long long a, long long b, long long c, long long d)

    {

        s1=a;

        s2=b;

        j1=c;

        j2=d;

    }

    matrice()

    {

        s1=0;

        s2=1;

        j1=1;

        j2=1;

    }

    matrice(long long a, long long b)

    {

        s1=a;

        s2=b;

        j1=0;

        j2=0;

    }



    matrice ridicare_patrat()

    {

        long long as1=s1, as2=s2, aj1=j1, aj2=j2;

        s1=((as1*as1)%mod+(as2*aj1)%mod)%mod;

        s2=((as1*as2)%mod+(as2*aj2)%mod)%mod;

        j1=((aj1*as1)%mod+(aj2*aj1)%mod)%mod;

        j2=((aj1*as2)%mod+(aj2*aj2)%mod)%mod;

    }



    matrice &operator*=(const matrice inmultitor)

    {

        long long as1=s1, as2=s2, aj1=j1, aj2=j2;

        s1=((as1*inmultitor.s1)%mod+(as2*inmultitor.j1)%mod)%mod;

        s2=((as1*inmultitor.s2)%mod+(as2*inmultitor.j2)%mod)%mod;

        j1=((aj1*inmultitor.s1)%mod+(aj2*inmultitor.j1)%mod)%mod;

        j2=((aj1*inmultitor.s2)%mod+(aj2*inmultitor.j2)%mod)%mod;

    }



    void afisare()

    {

        g << s2;

    }



};



int main()

{

    int k;

    f >> k;

    matrice mat1(1,1);

    matrice mat2;

    matrice mat3(1,0,0,1);

    k-=2;

    while(k)

    {

        if (k%2==0)

        {

            k/=2;

            mat2.ridicare_patrat();

        }

        else if (k%2==1)

        {

            k--;

            mat3*=mat2;

        }

    }

    mat1*=mat3;

    mat1.afisare();



    return 0;
}