#include <fstream>

#define modulo 666013

using namespace std;

int main()
{
    ifstream fin("kfib.in");
    ofstream fout("kfib.out");

    long long k,i,F1,F2,aux;

    fin>>k;
    k=k%(modulo*2+2);
    F1=1,F2=1;
    for(i=3;i<=k;i++) {
        aux=(F1+F2)%modulo;
        F1=F2;
        F2=aux;
    }
    fout<<F2<<'\n';

    fin.close();
    fout.close();

    return 0;
}