#include <iostream>
#include <fstream>
using namespace std;
const int MOD = 666013;
int F[2][3],M[3][3],A[3][3];
void Inmult()
    {
        int j,k;
        A[1][1]=A[1][2]=A[2][1]=A[2][2]=0;
        for(j=1;j<=2;j++)
            for(k=1;k<=2;k++)
                A[1][j]=(A[1][j]+1LL*F[1][k]*M[k][j])%MOD;
        F[1][1]=A[1][1];
        F[1][2]=A[1][2];
    }
void InmultI()
    {
        int i,j,k;
        A[1][1]=A[1][2]=A[2][1]=A[2][2]=0;

            for(i=1;i<=2;i++)
                for(j=1;j<=2;j++)
                    for(k=1;k<=2;k++)
                        A[i][j]=(A[i][j]+1LL*M[i][k]*M[k][j])%MOD;
        M[1][1]=A[1][1];
        M[1][2]=A[1][2];
        M[2][1]=A[2][1];
        M[2][2]=A[2][2];
    }
void Pow(int k)
    {
        while(k)
            {
                if(k&1)
                    Inmult();
                InmultI();
                k>>=1;
            }
    }
int main()
{
    int k;
    ifstream fin("kfib.in");
    fin>>k;
    fin.close();
    M[1][2]=1;
    M[2][1]=1;
    M[2][2]=1;
    F[1][1]=1;
    F[1][2]=1;
    Pow(k-1);
    ofstream fout("kfib.out");
    fout<<F[1][1];
    fout.close();
    return 0;
}