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

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

const int MOD=666013;

int N;

int mat[3][3], aux[3][3], init[3][3];

int quick_exp(int val, int pow)
{
    if(pow<=1)
        return val;
    int ans= quick_exp(val, pow/2 );
    if( pow % 2 )
        ans*=val;
    return ans;
}

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

    Quick_exp( 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*mat[i][J]*mat[I][j]) % MOD;
            aux[i][j] %= MOD;
        }
    if( pow % 2 )
    {
        for(int i=1 ; i<=2; ++i)
            for(int j=1; j<=2; ++j)
                mat[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*mat[i][J] * init[I][j]) % MOD;
            aux[i][j] %= MOD;
        }
    }
    for(int i=1 ; i<=2; ++i)
        for(int j=1; j<=2; ++j)
            mat[i][j]=aux[i][j];

}

int main()
{
    fin >> N;

    init[1][2]=1;
    init[2][2]=1;
    init[2][1]=1;
    for( int i=1; i<=2; ++i)
        for( int j=1; j<=2; ++j)
            mat[i][j]=init[i][j];
    Quick_exp( N-2 );
    fout<< 1LL*(mat[1][2] + mat[2][2] ) % MOD;
    return 0;
}