#include <fstream>
using namespace std;
#define mod 666013
#define l long long
l k, mat[2][2],pd[2][2];


void produs(l mat1[2][2], l mat2[2][2]){
    l aux[2][2];
    for(int i=0; i<2; i++)
        for(int j=0; j<2; j++)
            aux[i][j]=0;
    for(int i=0; i<2; i++)
        for(int j=0; j<2; j++)
            for(int k=0; k<2; k++)
                aux[i][j]+=((1ll* mat1[i][k]*mat2[k][j])%mod);
    for(int i=0; i<2; i++)
        for(int j=0; j<2; j++)
            mat1[i][j]=aux[i][j];
}

void putere_log(){
    for(int i=0; (1<<i)<=k; i++){
        if((1<<i)&k)
            produs(pd,mat);
        produs(mat,mat);
    }
}

int main()
{
    ifstream cin("kfib.in");
    ofstream cout("kfib.out");
    mat[1][1]=mat[1][0]=mat[0][1]=pd[1][1]=pd[0][0]=1;
    cin>>k;
    k-=1;
    putere_log();
    cout<<pd[1][1]%mod;
    return 0;
}