#include <cstdio>
#define mod 666013
#define ll long long int

using namespace std;

ll n,ar[2][2],sol[2][2];

void read() {
    scanf("%lld",&n);
    ar[0][0]=0;
    ar[0][1]=1;
    ar[1][0]=1;
    ar[1][1]=1;
    sol[0][0]=1;
    sol[0][1]=0;
    sol[1][0]=0;
    sol[1][1]=1;
}

void pw(ll ar1[2][2],ll ar2[2][2]) {
    ll i,j,k,sl[2][2];
    for(i=0;i<2;++i) {
        for(j=0;j<2;++j) {
            for(sl[i][j]=0,k=0;k<2;++k) {
                sl[i][j]+=ar1[i][k]*ar2[k][j];
            }
        }
    }
    for(i=0;i<2;++i) {
        for(j=0;j<2;++j) {
            ar1[i][j]=sl[i][j]%mod;
        }
    }
}

void solve() {
    for(;n;n>>=1,pw(ar,ar)) {
        if(n%2) {
            pw(sol,ar);
        }
    }
}

int main() {
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    read();
    solve();
    printf("%lld",sol[0][1]);
    return 0;
}