#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <memory.h>

using namespace std;

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

const int MOD = 666013;

int K, M[2][3], Z[3][3], REZ[3][3];

void Prod(int A[][3], int B[][3], int C[][3])
{
    for(int i=1; i <= 2; i++)
        for(int j = 1; j <= 2; j++)
            for(int k = 1; k <= 2; k++)
                C[i][j] = (C[i][j] + 1LL * A[i][k] * B[k][j]) % MOD;
}

void POW(int X[][3], int p)
{
    int AUX[3][3];
    REZ[1][1] = REZ[2][2] = 1;

    for(; p ; p >>= 1)
    {
        if(p & 1)
        {
            memset(AUX, 0 ,sizeof AUX);
            Prod(REZ, X, AUX);
            memcpy(REZ, AUX ,sizeof AUX);
        }

        memset(AUX, 0 ,sizeof AUX);
        Prod(X, X, AUX);
        memcpy(X, AUX ,sizeof AUX);
    }
}

int main()
{
    fin >> K;

    M[1][1] = 0; M[1][2] = M[2][1] = M[2][2] = 1;

    POW(M, K - 1);
    fout<<REZ[2][2];
    return 0;
}