#include <fstream>

using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
long long a,b,c,i,k;
int main()
{

    f>>k;
    a=0;
    b=1;
    if (k==0)
    {
        g<<"0";
    }
    else
    if (k==1)
    {
       g<<"1";
    }
    else
    {
        for (i=2;i<=k%666013;i++)
    {
        c=(a+b)%666013;
        a=b;
        b=c;
    }
    g<<c;
    }

    return 0;
}