#include <bits/stdc++.h>
#define mod 666013
#define intt uint64_t
using namespace std;
ifstream in("kfib.in");
ofstream out("kfib.out");
vector< vector < intt > > m1={{0,1},{0,0}};
vector< vector < intt > > Z={{0,1},{1,1}};
vector< vector < intt > > multiply(vector< vector < intt > > a,vector< vector < intt > > b){
    vector< vector < intt > > c={{0,0},{0,0}};
    intt A=a[0][0];
    intt B=a[0][1];
    intt C=a[1][0];
    intt D=a[1][1];
    intt E=b[0][0];
    intt F=b[0][1];
    intt G=b[1][0];
    intt H=b[1][1];
    c[0][0]=(A*E+B*G)%mod;
    c[0][1]=(A*F+B*H)%mod;
    c[1][0]=(C*E+D*G)%mod;
    c[1][1]=(C*F+D*H)%mod;
    return c;
}
vector< vector < intt > > pwr(vector< vector < intt > > n,intt p){
    vector< vector < intt > > rez=n;
    while(p){
        if(p&1)rez=multiply(rez,n);
        p>>=1;
        n=multiply(n,n);
    }
    return rez;
}
int main(){
    int k;
    in>>k;
        if(!k)out<<0<<'\n';
        else{
            vector< vector < intt > > mn=multiply(m1,pwr(Z,k-1));
            out<<mn[0][0]<<'\n';
        }
}