#include <bits/stdc++.h>
#define mod 666013
using namespace std;
string numeproblema="kfib";
ifstream fin(numeproblema+".in");
ofstream fout(numeproblema+".out");
struct mat{
long long a11=0,a12=0,a21=0,a22=0;
}Z,neutra,r;
int n;
mat inmul(mat m1,mat m2){
/// a b  e f
/// c d  g h
mat r;
r.a11=(m1.a11*m2.a11+m1.a12*m2.a21)%mod;
r.a12=(m1.a11*m2.a12+m1.a12*m2.a22)%mod;
r.a21=(m1.a21*m2.a11+m1.a22*m2.a21)%mod;
r.a22=(m1.a21*m2.a12+m1.a22*m2.a22)%mod;
return r;
}
void afis(mat x){
cout<<x.a11<<" "<<x.a12<<"\n"<<x.a21<<" "<<x.a22<<"\n\n";
}
mat ridput(mat x,int b){
    if(b==1){
        return x;
    }
 mat r = inmul(x,x);
if(b%2==0)
   return ridput(r,b/2);
else{
    return inmul(x,ridput(r,b/2));
}
}
int main()
{
   fin>>n;
   mat aux;
   aux.a12=aux.a21=aux.a22=1;
   Z=aux;
   neutra.a11=neutra.a22=1;

   Z=ridput(aux,n-1);
 //  afis(Z);
    fout<<Z.a22%mod;
}