#include <fstream>
#define mod 666013

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

int k,v[5][5],a[5][5],s[5][5];

void inmultire(int a[5][5], int b[5][5], int (&d)[5][5]){
    int c[5][5];
    c[1][1]=(1ll*a[1][1]*b[1][1]+1ll*a[1][2]*b[2][1])%mod;
    c[1][2]=(1ll*a[1][1]*b[1][2]+1ll*a[1][2]*b[2][2])%mod;
    c[2][1]=(1ll*a[2][1]*b[1][1]+1ll*a[2][2]*b[2][1])%mod;
    c[2][2]=(1ll*a[2][1]*b[1][2]+1ll*a[2][2]*b[2][2])%mod;
    for(int i=1;i<=2;i++)
        for(int j=1;j<=2;j++)
            d[i][j]=c[i][j];
}

void rp(int k){
    s[1][1]=s[2][2]=1;
    while(k!=0){
        if(k%2)
            inmultire(s,a,s);
        inmultire(a,a,a);
        k/=2;
    }
}

void init(){
    v[1][1]=v[1][2]=1;
    a[1][2]=a[2][1]=a[2][2]=1;
}

int main(){
    fin>>k;
    init();
    rp(k-1);
    inmultire(v,s,v);
    fout<<v[1][1];
    return 0;
}