#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);
    fib.push_back(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;
    k=k%p;
    //g<<p<<'\n';
    g<<fib[k]<<'\n';
    f.close();g.close();
    return 0;
}