#include <fstream>
#define MOD 666013
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
long long k;
long long mat[2][2],sol[2][2],aux[2][2];
void initializare_mat(){
    mat[0][0]=1; mat[0][1]=1;
    mat[1][0]=1; mat[1][1]=0;
}
void initializare_sol(){
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            if(i==j)
                sol[i][j]=1;
            else
                sol[i][j]=0;
}
void inmultire(long long A[2][2],long long B[2][2],long long C[2][2]){
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++){
            C[i][j]=0;
            for(int k=0;k<2;k++)
                C[i][j]=(C[i][j]+(A[i][k]*B[k][j])%MOD)%MOD;
        }
}
void copiere(long long A[2][2],long long B[2][2]){
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            A[i][j]=B[i][j];
}
int main()
{
    fin>>k;
    initializare_mat();
    initializare_sol();
    k-=2;
    while(k!=0){
        if(k%2==1){
            inmultire(sol,mat,aux);
            copiere(sol,aux);
        }
        inmultire(mat,mat,aux);
        copiere(mat,aux);
        k/=2;
    }
    fout<<(sol[0][0]+sol[0][1])%MOD;
    return 0;
}