#include <iostream>
#define mod 666013
#include <fstream>
using namespace std;

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

class matrice{

private:
    int s1,s2,j1,j2,k_term;

public:
    matrice(int a, int b, int c, int d)
    {
        s1=a;
        s2=b;
        j1=c;
        j2=d;
    }
    matrice()
    {
        s1=0;
        s2=1;
        j1=1;
        j2=1;
    }
    matrice(int a, int b)
    {
        s1=a;
        s2=b;
        j1=0;
        j2=0;
    }

    matrice ridicare_patrat()
    {
        int 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)
    {
        int 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;
}