#include <bits/stdc++.h>
#define mod 666013

using namespace std;

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

int I[3][3];
int r[3][3];
int k;

inline void inmultiremat(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;
}

inline void rid()
{
    int aux[3][3];
    r[1][1] = r[2][2] = 1;
    int p = k - 1;
    while (p >= 1)
    {
        if (p % 2 == 1)
        {
            memset(aux, 0, sizeof(aux));
            inmultiremat(r, I ,aux);
            memcpy(r, aux, sizeof(aux));
        }
        memset(aux, 0, sizeof(aux));
        inmultiremat(I, I, aux);
        memcpy(I, aux, sizeof(I));
        p /= 2;
    }
    fout << (r[1][1] + r[1][2]) % mod;
}

int main()
{
    fin >> k;
    I[1][2] = I[2][1] = I[2][2] = 1;
    //ridicam la puterea k - 1
    rid();
    return 0;
}