#include<bits/stdc++.h>
using namespace std;
const int MOD=666013;
const int N=4;
ifstream in("kfib.in");
ofstream out("kfib.out");
long long r[N][N]={{0,0,0},{0,1,0},{0,0,1}};
long long a[N][N],m1[N][N],k;

void i_matrice(long long a[N][N],long long b[N][N]){
long long A[N][N];
int i,j,k;
for(i=1;i<=2;i++)
    for(j=1;j<=2;j++)
    {
        A[i][j]=0;
        for(k=1;k<=2;k++)
            A[i][j]+=((a[i][k])%MOD*(b[k][j])%MOD)%MOD;
A[i][j]=A[i][j]%MOD;
    }

a[1][1]=(A[1][1])%MOD;
a[1][2]=(A[1][2])%MOD;
a[2][1]=(A[2][1])%MOD;
a[2][2]=(A[2][2])%MOD;
}


void init(){
r[1][1]=1;
r[1][2]=0;
r[2][1]=0;
r[2][2]=1;


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

m1[1][1]=0;
m1[1][2]=1;
}


void rptl(long long a[N][N],int n){
while(n>0){
if(n%2==1){i_matrice(r,a);
n--;}
i_matrice(a,a);
n/=2;

}
}


int main(){
in>>k;
if(k==0)out<<0;
else{
init();
rptl(a,k-2);
i_matrice(m1,r);
out<<((m1[1][1])%MOD+(m1[1][2])%MOD)%MOD<<"\n";}


///pentru a calcula Fk =>avem nevoie de suma dintre Fk-2 si Fk-1,deci de Mk-1;
///cum Mi=M1*Z^(i-1) =>Mk-1=M1*Z^(i-2);deci il vom ridica pe a la k-2
return 0;}