#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-2; // i-2 + 1
    if(k>p)
    {
        k=k%p;
        if(!k)k=p-1;
    }
    //g<<p<<'\n';
    g<<fib[k]<<'\n';
    f.close();g.close();
    return 0;
}