#include <bits/stdc++.h>
#define MODULO 666013
using namespace std;

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

#define cin fin
#define cout fout

int n, matrice[3][3], afiseaza[3][3];

void inmultire_matricerici(int a[3][3], int b[3][3], int c[3][3])
{
    for(int i = 0; i < 3; i++)
    {
        for(int j = 0; j < 3; j++)
        {
            for(int k = 0; k < 3; k++)
            {
                c[i][j] = (c[i][j] + 1LL * a[i][k] * b[k][j]) % MODULO;
            }
        }
    }
}

void ridicare_exponentiala(int M[3][3], int P)
{
	int C[3][3], aux[3][3], i;

	memcpy(C, matrice, sizeof(matrice));
	M[0][0] = M[1][1] = 1;

	for (i = 0; (1 << i) <= P; i++) {
		if (P & (1 << i)) {
			memset(aux, 0, sizeof(aux));
			inmultire_matricerici(M, C, aux);
			memcpy(M, aux, sizeof(aux));
		}

		memset(aux, 0, sizeof(aux));
		inmultire_matricerici(C, C, aux);
		memcpy(C, aux, sizeof(C));
	}
}

int main()
{
    cin >> n;

    matrice[0][0] = 0;
    matrice[1][1] = matrice[1][0] = matrice[0][1] = 1;

    ridicare_exponentiala( afiseaza, n-1);

    cout << afiseaza[1][1];
}