#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
int constanta=666013;
void inmultire(int A[2][2],int B[2][2],int rez[2][2])
{
    int aux[2][2];
    aux[0][0]=(1LL*A[0][0]*B[0][0] + 1LL*A[0][1]*B[1][0]) % constanta;
    aux[0][1]=(1LL*A[0][0]*B[0][1] + 1LL*A[0][1]*B[1][1]) % constanta;
    aux[1][0]=(1LL*A[1][0]*B[0][0] + 1LL*A[1][1]*B[1][0]) % constanta;
    aux[1][1]=(1LL*A[1][0]*B[0][1] + 1LL*A[1][1]*B[1][1]) % constanta;

    rez[0][0]=aux[0][0];
    rez[0][1]=aux[0][1];
    rez[1][0]=aux[1][0];
    rez[1][1]=aux[1][1];
}

void putere_log(int A[2][2], int n,int rez[2][2])
{
    if (n==0)
    {
        rez[0][0]=1; 
        rez[0][1]=0;
        rez[1][0]=0; 
        rez[1][1]=1;
        return;
    }
    if(n==1)
    {
        rez[0][0]=A[0][0];
        rez[0][1]=A[0][1];
        rez[1][0]=A[1][0];
        rez[1][1]=A[1][1];
        return;
    }

    int aux[2][2];
    putere_log(A,n/2,aux);

    int aux2[2][2];
    inmultire(aux,aux,aux2);

    if(n%2==0)
    {
        rez[0][0]=aux2[0][0];
        rez[0][1]=aux2[0][1];
        rez[1][0]=aux2[1][0];
        rez[1][1]=aux2[1][1];
    } 
    else
    {
        inmultire(aux2,A,rez);
    }
}

int main()
{
    int k;
    fin>>k;
    if(k==0)
    {
        fout<<0<<endl;
        return 0;
    }
    if(k==1)
    {
        fout<<1<<endl;
        return 0;
    }

    int baza[2][2]={
        {0, 1},
        {1, 1}
    };

    int rez[2][2];
    putere_log(baza,k-1,rez);

    fout<<rez[1][1]<<endl;

    fin.close();
    fout.close();
    return 0;
}