#include <iostream>
#include <fstream>
#define MOD 666013

using namespace std;

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

int k;
int fib[1500000];

int main()
{
    int s = 0;
    fin >> k;

    fib[0] = 0;
    fib[1] = 1;

    int rep=1234;//indicele de repetare

    for(int i = 2; i <= k; i++)
    {
        //if(i%1000==0)
        //  cout<<"i = "<<i<<"\n";
        fib[i] = (fib[i-1] + fib[i-2])% MOD;
        if(fib[i-1]==0 && fib[i]==1)
        {
          //cout<<"Ne repetam!\n";
          rep = i-1;
          //cout<<"rep = "<<rep<<"\n";
          break;
        }

    }
    //cout<<"rep este "<<rep<<"\n";
    k = k%rep;
    fout << fib[k] << "\n";

    fout.close();
    return 0;
}