#include <bits/stdc++.h>
using namespace std;
ifstream fin("kfib.in");
ofstream fout ("kfib.out");
#define ll long long
ll v[2][2],k,i,a,b,c,d;
int main()
{

        v[0][0]=0;v[0][1]=v[1][0]=v[1][1]=1;
        a=0;b=c=d=1;
        fin>>k;
       // (f0 f1)( z ^ k)
       if(k==0) fout<<0;
       else if (k==1) fout<<1;
       else{

        for(i=2;i<=k;i++){
        a=v[1][0];
        b=v[0][1]+v[0][0];
        c=v[1][1];
        d=v[1][1]+v[1][0];
        v[0][0]=a%666013;v[0][1]=b%666013;v[1][0]=c%666013;v[1][1]=d%666013;
       // cout<<a<<' '<<b<<endl<<c<<' '<<d<<endl<<endl;
        }

fout<<v[1][0];



       }

    return 0;
}