#include <iostream>
#include <fstream>


using namespace std;

ifstream in("kfib.in");
ofstream out("kfib.out");

const long long MOD=666013;

long long n[2][2];
long long ans[2][2];
long long aux[2][2];

void patrat()
{
    for(int i=0;i<=1;i++){
        for(int j=0;j<=1;j++){
            for(int k=0;k<=1;k++){
                aux[i][j]+=n[i][k]*n[k][j];
                aux[i][j]%=MOD;
            }
        }
    }

    for(int i=0;i<=1;i++){
        for(int j=0;j<=1;j++){
            n[i][j]=aux[i][j];
            aux[i][j]=0;
        }
    }

}


void nxans ()
{
    for(int i=0;i<=1;i++){
        for(int j=0;j<=1;j++){
            for(int k=0;k<=1;k++){
                aux[i][j]+=ans[i][k]*n[k][j];
                aux[i][j]%=MOD;
            }
        }
    }

    for(int i=0;i<=1;i++){
        for(int j=0;j<=1;j++){
            ans[i][j]=aux[i][j];
            aux[i][j]=0;
        }
    }
}

void lgput (int p)
{
    while(p){
        if(p%2){
            nxans();
        }
        patrat();
        p/=2;
    }

}


int main()
{
    int p;
    in>>p;

    n[0][0]=0;
    n[0][1]=1;
    n[1][0]=1;
    n[1][1]=1;

    for(int i=0;i<=1;i++){
        for(int j=0;j<=1;j++){
            ans[i][j]= n[i][j];
        }
    }

    lgput(p);

    out<<ans[0][0];

    return 0;
}