#include<iostream>
#include<fstream>
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
long long MOD=666013,n;
int i,j;

struct matrice{

long long m[2][2]={{0,1},{1,1}};

}A,B,C;

matrice prod(matrice A, matrice B){
    long long s;
    matrice D;
    for(i=0;i<2;i++){
        for(j=0;j<2;j++){
            s=0;
            for(int k=0;k<2;k++){
                s=(s+A.m[i][k]*B.m[k][j])%MOD;
            }
            C.m[i][j]=s;
        }
    }
    return C;
}

int main ()
{
    for(i=0;i<2;i++){
        for(j=0;j<2;j++){
            if(i==0&&j==0){
                B.m[i][j]=0;
            }
            else B.m[i][j]=1;
        }
    }

    fin>>n;
    n--;
    while(n){
        if(n%2==1){
            C=prod(B,A);
            B=C;
        }
        C=prod(A,A);
        A=C;
        n/=2;
    }
    fout<<B.m[0][1];
    fin.close();
    fout.close();
    return 0;
}