#include <iostream>
#include <fstream>

using namespace std;

ifstream in("kfib.in");
ofstream out("kfib.out");

const int NMAX = 1000;
const int MOD = 666013;
long long int fibo[3][3];
long long int mat[3][3];

void matmult1()
{
    long long int c[3][3];
    c[1][1]=0;
    c[1][2]=0;
    c[2][2]=0;
    c[2][1]=0;
    for(int i=1; i<=2; i++)
    {
        for(int j=1; j<=2; j++)
        {
            for(int k=1; k<=2; k++)
            {
                c[i][j]=(c[i][j]+(mat[k][j]*mat[i][k])%MOD)%MOD;
            }
        }
    }
    for(int i=1; i<=2; i++)
    {
        for(int j=1; j<=2; j++)
        {
            mat[i][j]=c[i][j];
        }
    }
}
void matmult2()
{
    long long int c[3][3];
    c[1][1]=0;

    c[1][2]=0;
    c[2][2]=0;
    c[2][1]=0;
    for(int i=1; i<=2; i++)
    {
        for(int j=1; j<=2; j++)
        {
            for(int k=1; k<=2; k++)
            {
                c[i][j]=(c[i][j]+(mat[k][j]*fibo[i][k])%MOD)%MOD;
            }
        }
    }
    for(int i=1; i<=2; i++)
    {
        for(int j=1; j<=2; j++)
        {
            fibo[i][j]=c[i][j];
        }
    }
}
void inmlog(int f)
{
    mat[1][1]=0;
    mat[1][2]=1;
    mat[2][1]=1;
    mat[2][2]=1;
    fibo[1][1]=1;
    fibo[1][2]=1;

    while(f>0)
    {
        if(f%2==1)
        {
            matmult2();
            f--;
        }
        else
        {
        matmult1();
        f=f/2;
        }
    }
}
int main()
{
    int f;
    in>>f;
    inmlog(f-1);
    out<<fibo[1][1];
    return 0;
}