#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])
{
    int aux[2][2]={
        {1,0},
        {0,1}
    };
    int baza[2][2]={
        {A[0][0],A[0][1]},
        {A[1][0],A[1][1]}
    };

    while(n>0)
    {
        if(n%2==1)
        {
            int temp[2][2];
            inmultire(aux,baza,temp);
            aux[0][0]=temp[0][0];
            aux[0][1]=temp[0][1];
            aux[1][0]=temp[1][0];
            aux[1][1]=temp[1][1];
        }

        int temp[2][2];
        inmultire(baza,baza,temp);
        baza[0][0]=temp[0][0];
        baza[0][1]=temp[0][1];
        baza[1][0]=temp[1][0];
        baza[1][1]=temp[1][1];

        n/=2;
    }
    rez[0][0]=aux[0][0];
    rez[0][1]=aux[0][1];
    rez[1][0]=aux[1][0];
    rez[1][1]=aux[1][1];
}
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;
}