#include <iostream>
#include <fstream>
#include <stdlib.h>
#include <string.h>
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
const int mod=666013;
int MAT[3][3],n,SOL[3][3];
void mult(int A[][3], int B[][3], int C[][3])
{
    int i, j, k;
    for (i = 0; i < 2; i++)
        for (j = 0; j < 2; j++)
            for (k = 0; k < 2; k++)
                C[i][j] = (C[i][j] + 1LL * A[i][k] * B[k][j]) % mod;

}
void pow(int p,int M[][3])
{
    int i,j;
    int C[3][3],AUX[3][3];
    memcpy(C, MAT, sizeof(MAT));
    M[0][0] = M[1][1] = 1;
    for (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()
{
    int i,j;
    f>>n;
    MAT[0][0]=0;
    MAT[0][1]=1;
    MAT[1][0]=1;
    MAT[1][1]=1;
    pow(n-1,SOL);
    g<<SOL[1][1];
}