#include <iostream>
#include <cstdio>
using namespace std;

FILE *in, *out;

const int mod = 666013;

int k;

/* CALCULAM a x b, PUNAND REZULTATUL IN a; FOLOSIM c CA SPATIU DE MANEVRA */
void inm(long long a[2][2], long long b[2][2], long long c[2][2])
{
    int i, j, k;

    for(i = 0; i < 2; i++)
        for(j = 0; j < 2; j++)
        {
            c[i][j] = 0;

            for(k = 0; k < 2; k++)
                c[i][j] += a[i][k] * b[k][j];
        }

    for(i = 0; i < 2; i++)
        for(j = 0; j < 2; j++)
            a[i][j] = c[i][j] % mod;
}

int main()
{
    in = fopen("kfib.in", "r");
    out = fopen("kfib.out", "w");

    fscanf(in, "%d", &k);

    //CALCULAM A ^ (k + 1) PRIN EXPONENTIERE LOGARITMICA

    long long A[2][2] = { {0,1}, {1,1} };

    long long ans[2][2] = { {1,0}, {0,1} };

    long long rez[2][2];

    k = k + 1;

    while(k)
    {
        if(k % 2 == 1) inm(ans, A, rez);

        inm(A, A, rez);

        k = k/2;
    }

    fprintf(out, "%lld", ans[0][0]);

    return 0;
}