#include <stdio.h>

#define MOD 666013

typedef struct
{
    long long mat[2][2];
} MATRICE;

MATRICE ind()   // matricea identitate pt initializarea produsului
{
    MATRICE a = {0};
    a.mat[0][0] = a.mat[1][1] = 1;
    a.mat[0][1] = a.mat[1][0] = 0;
    return a;
}

MATRICE inmult(MATRICE a, MATRICE b)
{
    MATRICE rez = {0};
    for(int i = 0; i < 2; i++)
    {
        for(int j = 0; j < 2; j++)
        {
            for(int k = 0; k < 2; k++)
            {
                rez.mat[i][j] = (rez.mat[i][j] + a.mat[i][k] * b.mat[k][j]) % MOD;
            }
        }
    }
    return rez;
}

MATRICE power(MATRICE a, long long p)
{
    MATRICE rez = ind();
    while(p > 0)
    {
        if(p % 2 == 1)
        {
            rez = inmult(rez, a); 
        }
        a = inmult(a, a);
        p = p / 2;
    }
    return rez;
}

long long fibonacci(long long K)
{
    if(K == 0) return 0;
    if(K == 1) return 1;

    MATRICE M = {0};
    M.mat[0][0] = M.mat[0][1] = M.mat[1][0] = 1;
    M.mat[1][1] = 0; 

    MATRICE rez = power(M, K - 1);
    return rez.mat[0][0];
}

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


    long long K;
    fscanf(fin, "%lld", &K);
    fprintf(fout, "%lld\n", fibonacci(K));

    fclose(fin);
    fclose(fout);
    
    return 0;
}