#include <iostream>
#include <fstream>

using namespace std;

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

#define mod 666013
int n;
long long mat[2][2];


void nmult (long long A[2][2], long long B[2][2])
{
    long long aux[2][2];
    aux[0][0] = 1LL * ( (1LL*A[0][0]*B[0][0]) % mod + (1LL*A[0][1]*B[1][0]) % mod )  % mod;
    aux[0][1] = 1LL * ( (1LL*A[0][0]*B[0][1]) % mod + (1LL*A[0][1]*B[1][1]) % mod )  % mod;
    aux[1][0] = 1LL * ( (1LL*A[1][0]*B[0][0]) % mod + (1LL*A[1][1]*B[1][0]) % mod )  % mod;
    aux[1][1] = 1LL * ( (1LL*A[1][0]*B[0][1]) % mod + (1LL*A[1][1]*B[1][1]) % mod )  % mod;
    for (int i=0; i<2; i++)
        for (int j=0; j<2; j++)
            A[i][j] = aux[i][j];
}

void lgput(long long mat[2][2], int pow)
{
    long long rez[2][2]={{0,1},{1,1}};
    for (; pow; pow>>=1)
    {
        if (pow & 1)
            nmult(rez,mat);
        nmult(mat,mat);
    }
    for (int i=0; i<2; i++)
        for (int j=0; j<2; j++) mat[i][j] = rez[i][j];
}


int main()
{
    fin>>n;
    mat[0][0]=0;
    mat[0][1]=mat[1][0]=mat[1][1]=1;
    lgput(mat, n-2);
    fout<<mat[1][1];

    fin.close();
    fout.close();
    return 0;
}