#include <iostream>
#include <fstream>
using namespace std;

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

const int MOD=666013;
int n,pow;

int a[10][10];
int aux[10][10];
int init[10][10];

void ExpMat(int pow)
{
    if(pow<=1)
        return;

    ExpMat( pow/2 );

    for(int i=1; i<=2; ++i)
        for(int j=1; j<=2; ++j)
        {
            aux[i][j]=0;
            for(int J=1, I=1; J<=2; ++J, ++I)
                aux[i][j] += (1LL*a[i][J]*a[I][j]) % MOD;
            aux[i][j] %= MOD;
        }
    if( pow % 2 )
    {
        for(int i=1 ; i<=2; ++i)
            for(int j=1; j<=2; ++j)
                a[i][j]=aux[i][j];

        for(int i=1; i<=2; ++i)
        for(int j=1; j<=2; ++j)
        {
            aux[i][j]=0;
            for(int J=1, I=1; J<=2; ++J, ++I)
                aux[i][j] += (1LL*a[i][J] * init[I][j]) % MOD;
            aux[i][j] %= MOD;
        }
    }
    for(int i=1 ; i<=2; ++i)
        for(int j=1; j<=2; ++j)
            a[i][j]=aux[i][j];

}

void Do()
{
    int i,j;
    a[1][1]=init[1][1]=0;
    a[1][2]=init[1][2]=1;
    a[2][1]=init[2][1]=1;
    a[2][2]=init[2][2]=1;
    ExpMat(n-2);
    fout<<1LL*(a[1][2]+a[2][2])%MOD;

}

int main()
{
    fin>>n;
    Do();
    return 0;
}