#include <fstream>
#define mod 666013
using namespace std;

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

int k,a[3][3],sol[3][3];
void prod(int x[3][3], int y[3][3]){
    int z[3][3]={0};
    for(int i=1;i<=2;++i)
    for(int j=1;j<=2;++j)
        for(int k=1;k<=2;++k){
                z[i][j]=(1ll*x[i][k]*y[k][j]+z[i][j])%mod;
    }
    for(int i=1;i<=2;++i)
        for(int j=1;j<=2;++j) y[i][j]=z[i][j];
}


int main(){
    fin>>k;
    if(k==0) fout<<0;
    if(k==1) fout<<1;
    else{
        a[1][1] = a[1][2] = a[2][1] = 1;
        sol[1][1]=sol[2][2]=1;
        k--;
        while(k){
            if(k%2==1) prod(a,sol);
            prod(a,a);
            k/=2;
        }
        fout<<sol[1][1];
    }
    return 0;
}