#include <bits/stdc++.h>
using namespace std;
 
ifstream in("kfib.in");
ofstream out("kfib.out");
#define cin in
#define cout out
#define MOD 666013

int N, rec[3][3], sol[3][3];
	
void mult(int A[][3], int B[][3], int R[][3]) {
	for (int i = 0; i < 2; i++)
		for (int j = 0; j < 2; j++)
			for (int k = 0; k < 2; k++) 
				R[i][j] = (R[i][j] + 1LL * A[i][k] * B[k][j]) % MOD;
}

	
void power(int P, int rez[][3]) {
	int C[3][3], aux[3][3], i;
	
	memcpy(C, rec, sizeof(rec));
	rez[0][0] = rez[1][1] = 1;
 
	for (i = 0; (1 << i) <= P; i++) {
		if (P & (1 << i)) {
			memset(aux, 0, sizeof(aux));
			mult(rez, C, aux);
			memcpy(rez, aux, sizeof(aux));
		}
 
		memset(aux, 0, sizeof(aux));
		mult(C, C, aux);
		memcpy(C, aux, sizeof(C));
	}
}

int main() {
    cin >> N;
    rec[0][0] = 0; rec[0][1] = 1; rec[1][0] = 1; rec[1][1] = 1;
    power(N - 1, sol);
    cout << sol[1][1];
    return 0;
}