#include<bits/stdc++.h>
using namespace std;

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

//constanta la care se imparte
const long long r=666013;

//functia care inmulteste 2 matrici
void imultire_matrici(long long v[2][2],long long w[2][2]){
    long long a[2][2];
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            a[i][j]=(v[i][0]*w[0][j])%r+(v[i][1]*w[1][j])%r;

    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            v[i][j]=a[i][j]%r;
}

//ridicare la putere logaritmica pe matrici
void lgputM(long long v[2][2],long long p){


    if(p!=1){   //cand p este 1, se termina recursivitatea

    //retinem valoarile din matricea v, intr-o matrice secundara
    //pentru cazul in care puterea este impara
    long long a[2][2];
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            a[i][j]=v[i][j];

    //ridicam matricea la patrat
    imultire_matrici(v,v);

    //ridicarea la putrere logaritmica
    if(p%2==0) lgputM(v,p/2); //daca puterea e para
    else{               // daca puterea este impara
        lgputM(v,(p-1)/2);
        imultire_matrici(v,a);
    }
    }

}

int main(){
    long long k;f>>k;
    if(k==0) g<<"0"; //caz special
    else if(k==1 || k==2) g<<"1"; //caz special
    else{
            //matricea constanta
        long long v[2][2]={0,1,1,1};
            //matricea fibonacci
        long long fib[2][2]={0,1,0,0};
            //ridicare la putere logaritmica
            lgputM(v,k-1);
            imultire_matrici(fib,v);
            //al 2-lea termen al matrici este raspunsul
            g<<fib[0][1];
    }
}