#include <stdio.h>
#include <stdlib.h>
#define MOD 666013
typedef long long ll;

void copiere_rezultat(ll a[2][2], ll rezultat[2][2])
{
    for(int i = 0; i < 2; i ++)
    {
        for(int j = 0; j < 2; j ++)
        {
            a[i][j] = rezultat[i][j];
        }
    }
}

void inmultire(ll a[2][2], ll b[2][2])
{
    ll 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;

    copiere_rezultat(a, rezultat);
}

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

ll fibonacci(int k)
{
    if(k == 0)
    {
        return 0;
    }
    ll 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;
}