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

int k, Z[DMAX][DMAX], D=2;

void multiplication(int A[DMAX][DMAX], int B[DMAX][DMAX], int C[DMAX][DMAX])
{
    int aux[DMAX][DMAX];
    //initializare cu 0 aux
    memset(aux, 0, sizeof(aux));
    for (int i=1; i<=D; i++)
        for (int j=1; j<=D;j++)
            for(int k=1; k<=D; k++)
                aux[i][j]= (aux[i][j] + 1LL*A[i][k]*B[k][j]) % MOD;
    memcpy(C, aux, sizeof(aux));
}

void exponentiere(int Z[DMAX][DMAX], int K)
{
    int M[DMAX][DMAX];
    memset(M, 0, sizeof(M));
    for (int i=1; i<=D; i++) M[i][i]=1;
    while (K!=1)
        if (K % 2==0)
        {
            multiplication(Z,Z,Z);
            K/=2;
        }
        else
        {
            multiplication(M, Z, M);
            K--;
        }
    multiplication(M,Z,Z);
}

int main()
{
    f>>k;
    Z[1][1]=1; Z[1][2]=1;
    Z[2][1]=1; Z[2][2]=0;
    exponentiere(Z, k-1);
    g<<Z[1][1]<<'\n';
    f.close();g.close();
    return 0;
}