#include <iostream>
#include <fstream>
using namespace std;
ifstream fin ("kfib.in");
ofstream fout ("kfib.out");
long long z[2][2], Z[2][2], F[2][2];
const int MOD = 666013;

void inmultire_matrice_1 (long long A[2][2], long long B[2][2])
{
    int C[2][2];
    C[0][0]=(A[0][0]*B[0][0]+A[0][1]*B[1][0])%MOD;
    C[0][1]=(A[0][0]*B[0][1]+A[0][1]*B[1][1])%MOD;
    C[1][0]=(A[1][0]*B[0][0]+A[1][1]*B[1][0])%MOD;
    C[1][1]=(A[1][0]*B[0][1]+A[1][1]*B[1][1])%MOD;
    F[0][0]=C[0][0];
    F[0][1]=C[0][1];
    F[1][0]=C[1][0];
    F[1][1]=C[1][1];
    B[0][0]=C[0][0];
    B[0][1]=C[0][1];
    B[1][0]=C[1][0];
    B[1][1]=C[1][1];
}
void inmultire_matrice_2 (long long A[2][2], long long B[2][2])
{
    int C[2][2];
    C[0][0]=(A[0][0]*B[0][0]+A[0][1]*B[1][0])%MOD;
    C[0][1]=(A[0][0]*B[0][1]+A[0][1]*B[1][1])%MOD;
    C[1][0]=(A[1][0]*B[0][0]+A[1][1]*B[1][0])%MOD;
    C[1][1]=(A[1][0]*B[0][1]+A[1][1]*B[1][1])%MOD;
    B[0][0]=C[0][0];
    B[0][1]=C[0][1];
    B[1][0]=C[1][0];
    B[1][1]=C[1][1];
}
void putere( int p )
{
    for (int bit = 0; p >> bit; bit++) {
        if ((p >> bit) & 1)
        {
                inmultire_matrice_1 (z, Z);
        }

        inmultire_matrice_2 (z, z);
}
}
int main()
{
    int k;
    z[0][0]=0; z[0][1]=1; z[1][0]=1; z[1][1]=1;
    Z[0][0]=1; Z[0][1]=0; Z[1][0]=0; Z[1][1]=1;
    F[0][0]=0; F[0][1]=1; F[1][0]=1; F[1][1]=1;
    fin>>k;
    putere(k-1);
    /*for(int i=0; i<2; i++)
    {
        for(int j=0; j<2; j++)
            cout<<F[i][j]<<" ";
        cout<<endl;
    }*/
    fout<<F[1][1];
    return 0;
}