#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])%MOD+(mat_rez_copie[1]*mat_a[2])%MOD)%MOD;
            mat_rez[1]=((mat_rez_copie[0]*mat_a[1])%MOD+(mat_rez_copie[1]*mat_a[3])%MOD)%MOD;
            mat_rez[2]=((mat_rez_copie[2]*mat_a[0])%MOD+(mat_rez_copie[3]*mat_a[2])%MOD)%MOD;
            mat_rez[3]=((mat_rez_copie[2]*mat_a[1])%MOD+(mat_rez_copie[3]*mat_a[3])%MOD)%MOD;
        }
        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])%MOD+(mat_a_copie[1]*mat_a_copie[2])%MOD)%MOD;
        mat_a[1]=((mat_a_copie[0]*mat_a_copie[1])%MOD+(mat_a_copie[1]*mat_a_copie[3])%MOD)%MOD;
        mat_a[2]=((mat_a_copie[2]*mat_a_copie[0])%MOD+(mat_a_copie[3]*mat_a_copie[2])%MOD)%MOD;
        mat_a[3]=((mat_a_copie[2]*mat_a_copie[1])%MOD+(mat_a_copie[3]*mat_a_copie[3])%MOD)%MOD;
        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])%MOD+(fibo_copie[1]*mat_rez[2])%MOD)%MOD;
    fibo[1]=((fibo_copie[0]*mat_rez[1])%MOD+(fibo_copie[1]*mat_rez[3])%MOD)%MOD;

    out<<fibo[1]%MOD;

    return 0;
}