#include <fstream>
using namespace std;

const int MOD=666013;

unsigned long long int fibo[2]={1,1};
unsigned long long int fibo_copie[2]={1,1};
unsigned long long int mat_rez[4]={1,0,0,1};
unsigned long long int mat_a[4]={0,1,1,1};
unsigned long long int mat_rez_copie[4];
unsigned long long int mat_a_copie[4];

int main()
{
    ifstream in("kfib.in");
    ofstream out("kfib.out");

    unsigned long long int k;
    in>>k;

    if(k==0)
    {
        out<<0;
        return 0;
    }
    if(k==1 || k==2)
    {
        out<<1;
        return 0;
    }

    k=k-2;

    while(k)
    {
        if(k%2)
        {
            mat_rez_copie[0]=mat_rez[0];
            mat_rez_copie[1]=mat_rez[1];
            mat_rez_copie[2]=mat_rez[2];
            mat_rez_copie[3]=mat_rez[3];
            mat_rez[0]=mat_rez_copie[0]*mat_a[0]+mat_rez_copie[1]*mat_a[2];
            mat_rez[1]=mat_rez_copie[0]*mat_a[1]+mat_rez_copie[1]*mat_a[3];
            mat_rez[2]=mat_rez_copie[2]*mat_a[0]+mat_rez_copie[3]*mat_a[2];
            mat_rez[3]=mat_rez_copie[2]*mat_a[1]+mat_rez_copie[3]*mat_a[3];
        }
        mat_a_copie[0]=mat_a[0];
        mat_a_copie[1]=mat_a[1];
        mat_a_copie[2]=mat_a[2];
        mat_a_copie[3]=mat_a[3];
        mat_a[0]=mat_a_copie[0]*mat_a_copie[0]+mat_a_copie[1]*mat_a_copie[2];
        mat_a[1]=mat_a_copie[0]*mat_a_copie[1]+mat_a_copie[1]*mat_a_copie[3];
        mat_a[2]=mat_a_copie[2]*mat_a_copie[0]+mat_a_copie[3]*mat_a_copie[2];
        mat_a[3]=mat_a_copie[2]*mat_a_copie[1]+mat_a_copie[3]*mat_a_copie[3];
        k=k/2;
    }

    //out<<mat_rez[0]<<' '<<mat_rez[1]<<'\n'<<mat_rez[2]<<' '<<mat_rez[3]<<'\n';

    fibo_copie[0]=fibo[0];
    fibo_copie[1]=fibo[1];

    fibo[0]=fibo_copie[0]*mat_rez[0]+fibo_copie[1]*mat_rez[2];
    fibo[1]=fibo_copie[0]*mat_rez[1]+fibo_copie[1]*mat_rez[3];

    out<<fibo[1]%MOD;

    return 0;
}