#include <fstream>
#define R 666013
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
int a[3][3],aux[3][3],sol[3][3],n,i,j,k,p;
void inmulteste(int a[3][3],int b[3][3],int c[3][3]){
    for(i=1;i<=2;i++)
        for(j=1;j<=2;j++){
            c[i][j]=0;
            for(k=1;k<=2;k++){
                c[i][j]+=1LL*a[i][k]*b[k][j]%R;
                c[i][j]%=R;
            }
    }
}
void copiaza(int a[3][3],int b[3][3]){
    for(i=1;i<=3;i++)
        for(j=1;j<=3;j++)
            b[i][j]=a[i][j];
}
int main(){
    fin>>n;
    if(n<=1) fout<<n;
    else{
        a[1][1]=0; a[1][2]=1;
        a[2][1]=1; a[2][2]=1;
        sol[1][1]=sol[2][2]=1;
        while(n){
            if(n%2){
                inmulteste(sol,a,aux);
                copiaza(aux,sol);
            }
            inmulteste(a,a,aux);
            copiaza(aux,a);
            n/=2;
        }
        fout<<sol[2][1];
    }
    return 0;
}