#include<iostream>
#include<fstream>
#include<algorithm>
#include<string>
#include<cstring>
#include<vector>
#include<map>

using namespace std;

const int cst=666013;

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

int main(){

long long i,j,a[4][4],p[4][4],n,m,t1,t2,t3,t4;


f>>n;

p[1][1]=1;
p[1][2]=0;
p[2][1]=0;
p[2][2]=1;

a[1][1]=0;
a[1][2]=1;
a[2][1]=1;
a[2][2]=1;


for(n; n>=1; n>>=1){
    if(n&1){
        t1=(p[1][1]*a[1][1]) + (p[1][2]*a[2][1]);
        t2=(p[1][1]*a[1][2]) + (p[1][2]*a[2][2]);
        p[1][1]=t1%cst;
        p[1][2]=t2%cst;

        t1=(p[2][1]*a[1][1]) + (p[2][2]*a[2][1]);
        t2=(p[2][1]*a[1][2]) + (p[2][2]*a[2][2]);
        p[2][1]=t1%cst;
        p[2][2]=t2%cst;
    }

    t1=(a[1][1]*a[1][1]) + (a[1][2]*a[2][1]);
    t2=(a[1][1]*a[1][2]) + (a[1][2]*a[2][2]);
    t3=(a[2][1]*a[1][1]) + (a[2][2]*a[2][1]);
    t4=(a[2][1]*a[1][2]) + (a[2][2]*a[2][2]);

    a[1][1]=t1%cst;
    a[1][2]=t2%cst;
    a[2][1]=t3%cst;
    a[2][2]=t4%cst;

}

g<<p[1][2];

return 0;
}