#include <bits/stdc++.h>
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];

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

    expo(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]=init[2][1]=init[2][2]=1;
    mat[1][2]=mat[2][1]=mat[2][2]=1;

    expo(n-2);
    if(n==1 || n==2) fout<<1;
    else fout<<(mat[1][2] + mat[2][2]) % MOD;


    return 0;
}