#include <fstream>
#define MOD 666013
using namespace std;
ifstream in("kfib.in");
ofstream out("kfib.out");
int v[1400005],n,nr;
int main()
{
    in>>n;
    if(n == 0) out<<0;
    else{
        bool ok=1;
        v[1]=1;
        v[2]=1;
        nr=2;
        while(ok){
            v[++nr]=(v[nr-1]+v[nr-2])%MOD;
            if(v[nr]== 1 && v[nr-1] == 1){
                ok=0;
                nr-=2;
                }
        }

        out<<v[n%nr];
    }
    return 0;
}