#include<fstream>
#define R 666013
#define ull unsigned long long
using namespace std;

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

int K;
ull A[3][3],sol[3][3];

void inm(ull m1[3][3],ull m2[3][3])
{
    ull m3[3][3];

    for (int i=1;i<=2;i++)
     for (int j=1;j<=2;j++)
            m3[i][j]=( ( (m1[i][1]*m2[1][j])%R )+( (m1[i][2]*m2[2][j]) % R) ) % R;

    for (int i=1;i<=2;i++)
     for (int j=1;j<=2;j++)
        m1[i][j]=m3[i][j];
}

void rid(ull baz[3][3],int exp)
{
    sol[1][1]=1;sol[2][2]=1;

    for (int i=0; (1LL<<i)<=exp; i++)
    {
        if ( ( (1<<i) & exp ) > 0 )
        inm(sol,baz);

        inm(baz,baz);

    }


}


int main()
{

    f>>K;

        A[1][1]=1; A[1][2]=1;
        A[2][1]=1; A[2][2]=0;

        rid(A,K-1);

        g<<sol[1][1]%R;



return 0;
}