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

void inmultire(long long a[2][2], long long b[2][2])
{
    long long rezultat[2][2];
    rezultat[0][0] = (a[0][0] * b[0][0] + a[0][1] * b[1][0]) % MOD;
    rezultat[0][1] = (a[0][0] * b[0][1] + a[0][1] * b[1][1]) % MOD;
    rezultat[1][0] = (a[1][0] * b[0][0] + a[1][1] * b[1][0]) % MOD;
    rezultat[1][1] = (a[1][0] * b[0][1] + a[1][1] * b[1][1]) % MOD;

    a[0][0] = rezultat[0][0];
    a[0][1] = rezultat[0][1];
    a[1][0] = rezultat[1][0];
    a[1][1] = rezultat[1][1];
}

void putere(long long F[2][2], int n)
{
    long long rezultat[2][2] = {{1,0},{0,1}};
    while(n > 0)
    {
         if(n % 2 == 1)
         {
             inmultire(rezultat, F);
         }
         inmultire(F, F);
         n /= 2;
    }
    F[0][0] = rezultat[0][0];
    F[0][1] = rezultat[0][1];
    F[1][0] = rezultat[1][0];
    F[1][1] = rezultat[1][1];
}

long long fibonacci(int k)
{
    if(k == 0)
    {
        return 0;
    }
    long long F[][2] = {{1,1},{1,0}};
    putere(F, k);
    return F[0][1];
}

int main()
{
    FILE *fin = fopen("kfib.in", "r");
    if(fin == NULL)
    {
        fprintf(stderr, "Eroare la fisierul de intrare\n");
        exit(1);
    }

    FILE *fout = fopen("kfib.out", "w");
    if(fout == NULL)
    {
        fprintf(stderr, "Eroare la fisierul de iesire\n");
        exit(1);
    }
    int k;
    fscanf(fin,"%d", &k);
    fprintf(fout, "%lld\n", fibonacci(k));
    if(fclose(fout) != 0)
    {
        perror(NULL);
        exit(1);
    }
    if(fclose(fin) != 0)
    {
        perror(NULL);
        exit(1);
    }
    return 0;
}