#include <fstream>
#include <string.h>
#define mod 666013
using namespace std;

ifstream in("kfib.in");
ofstream out("kfib.out");

int k;
int mat[4][4], solutie[4][4];

void inmultire(int a[][4], int b[][4], int c[][4]){
	for(int i = 0; i < 2; i++)
		for(int j = 0; j < 2; j++)
			for(int k = 0; k < 2; k++)
				c[i][j] = (c[i][j] + 1LL * a[i][k] * b[k][j]) % mod;
}

void ridicarePutere(int n, int sol[][4]){
    int c[4][4], aux[4][4];

	memcpy(c, mat, sizeof(mat));
	sol[0][0] = sol[1][1] = 1;

    for (int i = 0; (1 << i) <= n; i++) {
		if (n & (1 << i)) {
			memset(aux, 0, sizeof(aux));
			inmultire(sol, c, aux);
			memcpy(sol, aux, sizeof(aux));
		}

		memset(aux, 0, sizeof(aux));
		inmultire(c, c, aux);
		memcpy(c, aux, sizeof(aux));
	}
}

int main()
{
    in>>k;

    mat[0][0] = 0; mat[0][1] = 1;
    mat[1][0] = 1; mat[1][1] = 1;

    ridicarePutere(k - 1, solutie);
    out<<solutie[1][1];

    in.close();
    out.close();
    return 0;
}