#include <stdio.h>
#include <stdlib.h>
#define MOD 666013

void produs(int p[2][2], int a[2][2], int b[2][2])
{
    int aux[2][2];
    aux[0][0] = ((long long)a[0][0] * b[0][0] + (long long)a[0][1] * b[1][0]) % MOD;
    aux[0][1] = ((long long)a[0][0] * b[0][1] + (long long)a[0][1] * b[1][1]) % MOD;
    aux[1][0] = ((long long)a[1][0] * b[0][0] + (long long)a[1][1] * b[1][0]) % MOD;
    aux[1][1] = ((long long)a[1][0] * b[0][1] + (long long)a[1][1] * b[1][1]) % MOD;
    p[0][0] = aux[0][0];
    p[0][1] = aux[0][1];
    p[1][0] = aux[1][0];
    p[1][1] = aux[1][1];
}

int fibo(int n)
{
    int f[2][2] = {{1, 1}, {1, 0}};
    int p[2][2] = {{1, 0}, {0, 1}};
    n--;
    while (n != 0)
    {
        if (n % 2 != 0)
        {
            produs(p, p, f);
        }
        produs(f, f, f);
        n /= 2;
    }
    return p[0][0];
}

int main()
{
    FILE *in, *out;
    in = fopen("kfib.in", "r");
    out = fopen("kfib.out", "w");
    int k;
    fscanf(in, "%d", &k);
    fprintf(out, "%d\n", fibo(k));
    fclose(in);
    fclose(out);
    return 0;
}