#include <fstream>
#define MAT 2
#define MOD 666013
using namespace std;

ifstream f("kfib.in");
ofstream g("kfib.out");

long long int** inmultire_matrici(long long int** A, long long int** B)
{
    long long int **C = new long long int*[MAT];
    for (int i = 0; i < MAT; ++i)
    {
        C[i] = new long long int[MAT];
        for (int j = 0; j < MAT; ++j)
        {
            C[i][j] = 0;
            for (int ik = 0; ik < MAT; ++ik)
                C[i][j] += (A[i][ik] * 1LL * B[ik][j]) % MOD;
        }
    }
    return C;
}

long long int** ridicare_la_putere(long long int** A, int n)
{
    if (n == 1)
        return A;
    if (n % 2)
        return inmultire_matrici(A, ridicare_la_putere(A, n - 1));
    long long int** C = ridicare_la_putere(A, n / 2);
    return inmultire_matrici(C, C);
}

int main()
{
    int n;
    long long int** A = new long long int*[MAT];
    long long int **B = new long long int*[MAT];
    for (int i = 0; i < MAT; ++i)
    {
        B[i] = new long long int[MAT];
        A[i] = new long long int[MAT];
    }
    f >> n;
    A[0][0] = 0;
    A[0][1] = A[1][0] = A[1][1] = 1;
    B = ridicare_la_putere(A, n - 1);
    g << B[1][1];
    return 0;
}