#include <fstream>
#include <cstring>
#define mod 666013
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");

int k;
int Z[3][3], SOL[3][3];

inline void mult(int A[][3], int B[][3], int C[][3])
{
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
            for (int k = 0; k < 2; k++)
                C[i][j] = (C[i][j] + 1LL * A[i][k] * B[k][j]) % mod;

}

inline void ExponentiereRapida(int Z[][3],int P, int M[][3])
{
    int C[3][3], AUX[3][3];
    memcpy(C, Z, sizeof(Z));
    M[0][0] = M[1][1] = 1;
    for (int i=0;(1 << i)<=P;i++)
    {
        if (P&(1 << i))
            {
                memset(AUX, 0, sizeof(AUX));
                mult(M, C, AUX);
                memcpy(M, AUX, sizeof(AUX));
            }
        memset(AUX, 0, sizeof(AUX));
        mult(C, C, AUX);
        memcpy(C, AUX, sizeof(C));
    }
}

int main() {

    f>>k;
    Z[0][0] = 0; Z[0][1] = 1; Z[1][0] = 1; Z[1][1] = 1;
    ExponentiereRapida(Z,k-1,SOL);
    g<<SOL[1][1]<<'\n';
    f.close();g.close();
    return 0;
}