#include<stdio.h>
#include<stdlib.h>

#define MOD 666013

typedef struct matrice
{
    long long a11, a12, a21, a22;
}matrice_t;

matrice_t inmultire(matrice_t A, matrice_t B)
{
	matrice_t aux;

	aux.a11 = (((A.a11 % MOD) * (B.a11 % MOD)) % MOD + ((A.a12 % MOD) * (B.a21 % MOD)) % MOD) %MOD;
	aux.a12 = (((A.a11 % MOD) * (B.a12 % MOD)) % MOD + ((A.a12 % MOD) * (B.a22 % MOD)) % MOD) %MOD;
	aux.a21 = (((A.a21 % MOD) * (B.a11 % MOD)) % MOD + ((A.a22 % MOD) * (B.a21 % MOD)) % MOD) %MOD;
	aux.a22 = (((A.a21 % MOD) * (B.a12 % MOD)) % MOD + ((A.a22 % MOD) * (B.a22 % MOD)) % MOD) %MOD;
	
    return aux;
}

matrice_t power(matrice_t Z, int p)
{
	if (p == 1)
    {
		return Z;
    }
	if (p % 2 == 1)
    {	
		return inmultire(Z,	power(Z,p-1)); 
    }
	else
	{
		matrice_t B = power(Z, p/2);

		return inmultire(B, B);
	}
}

int main()
{
	FILE *in = NULL, *out = NULL;
    if( (in = fopen("kfib.in", "r")) == NULL)
    {
        perror("fopen");
        exit(EXIT_FAILURE);
        return 0;
    }
    if( (out = fopen("kfib.out", "w")) == NULL)
    {
        perror("fopen");
        exit(EXIT_FAILURE);
        return 0;
    }

    int k;

	if( fscanf(in, "%d", &k) != 1)
    {
        perror("fscanf");
        exit(EXIT_FAILURE);
        return 0;
    }

	if (k == 0)
	{
		fprintf(out, "0\n");
		return 0;
	}
	else
		if (k == 1)
		{
			fprintf(out, "1\n");
			return 0;
		}
		
	matrice_t Z, rez;

	Z.a11 = 0, Z.a12 = Z.a21 = Z.a22 = 1;
    
	rez = power(Z, k-1);
	
	fprintf(out, "%lld", rez.a22);

    if(fclose(in) != 0)
    {
        perror("fclose");
        exit(EXIT_FAILURE);
        return 0;
    }
    if(fclose(out) != 0)
    {
        perror("fclose");
        exit(EXIT_FAILURE);
        return 0;
    }

	return 0;
}