#include <fstream>
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
long a,b=666013;
long rest[100001],i,lung;

int main()
{
    f>>a;
    rest[1]=1%b;
    rest[2]=1%b;
    i=3;
    while(i<=a)
    {
        rest[i]=(rest[i-1]+rest[i-2])%b;
        if(rest[i-1]==1&&rest[i]==1)
        {lung=i-2;break;}
        i++;
    }
   if(lung==0&&b<a)
        g<<rest[b];
   else
   if(a>=b)
         g<<rest[a%lung];
     else g<<rest[a];
     f.close();
     g.close();
    return 0;
}