#include <fstream>
#include <vector>
#define MOD 666013
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");

int k,p,curent;
//p=perioada
vector < int > fib;

int main()
{
    f>>k;
    fib.push_back(0); //pozitia 0
    fib.push_back(1); //pozitia 1
    int i=1;
    do
    {
        ++i;
        curent=(fib[i-1]+fib[i-2]) % MOD;
        fib.push_back(curent);
    }while( (fib[i-1]==0 && fib[i]==1)==false);
    p=i-1; // i-2 + 1
    if(k!=0 && k % p==0)k=p-1;
    k=k%p;
    //--k;
    //g<<p<<'\n';
    //for(int j=0;j<=i;++j)g<<fib[j]<<' ';g<<'\n';
    g<<fib[k]<<'\n';
    f.close();g.close();
    return 0;
}