#include <iostream>
#include <fstream>
#include <cstring>
#define prim 666013
using namespace std;

int Z[2][2],K,sol[2][2];

void mult(int A[][2],int B[][2],int C[][2]){
    int i,j,k;
    for (i=0; i<2; i++){
        for (j=0; j<2; j++)
            for (k=0; k<2; k++)
                C[i][j]=(C[i][j]+1LL*A[i][k]*B[k][j])%prim;
    }
}

void f_pow(int M[][2],int p){
    int aux[2][2],A[2][2];
    M[0][0]=M[1][1]=1;
    memcpy(A,Z,sizeof(Z));

    while (p){
        if (p&1){
            memset(aux,0,sizeof(aux));
            mult(M,A,aux);
            memcpy(M,aux,sizeof(aux));
        }
        memset(aux,0,sizeof(aux));
        mult(A,A,aux);
        memcpy(A,aux,sizeof(aux));
        p>>=1;
    }
}

int main(){
    ifstream fin("kfib.in");
    ofstream fout("kfib.out");
    fin >> K;

    Z[0][0]=0; Z[0][1]=Z[1][0]=Z[1][1]=1;
    f_pow(sol,K-1);
    fout << sol[1][1] << "\n";
    return 0;
}