#include <fstream>
#include <iostream>
using namespace std;
unsigned long long a[6][6],b[6][6];

int inm(int x,int y,int x1,int y1)
{
    int i,j;
    b[1][1]=(a[1][1]*x+a[1][2]*x1)%666013;
    b[1][2]=(a[1][1]*y+a[1][2]*y1)%666013;
    b[2][1]=(a[2][1]*x+a[2][2]*x1)%666013;
    b[2][2]=(a[2][1]*y+a[2][2]*y1)%666013;

    for(i=1;i<=2;i++)
    for(j=1;j<=2;j++)
        a[i][j]=b[i][j];
  //   cout<<a[1][1]<<" "<<a[1][2]<<'\n'<<a[2][1]<<" "<<a[2][2]<<'\n'<<'\n';


    return 1;
}

int lgput(int p)
{

//cout<<p<<" ";

    if(p==0) return 1;
    else
    {

        if(p%2==0)
        {

            inm(1,1,1,0);
            return lgput(p/2);
        }
        else
        {
            int o=1,r=1,k=1,l=0;
            o=a[1][1];
            r=a[1][2];
            k=a[2][1];
            l=a[2][2];
            inm(1,1,1,0);

            return lgput((p-1)/2)*inm(1,1,1,0);
        }
    }
}



int main()
{
    ifstream f("kfib.in");
    ofstream g("kfib.out");
    int n,i,j,e;
    f>>n;
    a[1][1]=1;
    a[2][1]=1;
    a[1][2]=1;
    a[2][2]=0;
    b[1][1]=1;
    b[2][1]=1;
    b[1][2]=1;
    b[2][2]=0;
   /* if(e>=3)
    {
        e=lgput(n-1);
        g<<a[1][1];
    }
    if(e==0)
        g<<"0";
    if(e==1)
        g<<"1";
    if(e==2)
        g<<"1";
    if(e==3)
        g<<"2";*/

    if(n>=4)
    {
        e=lgput(n-2);
        //cout<<e;
        g<<a[1][1];
    }
    if(n==0)
        g<<"0";
    if(n==1)
        g<<"1";
    if(n==2)
        g<<"1";
    if(n==3)
        g<<"2";

    f.close();
    g.close();
    return 0;
}