#include <cstdio>

using namespace std;

void pow(long long f[4],int n, int curr_step) {
	if (n < 1<<(curr_step + 1))
		return;

	long long f_temp[] = {f[0], f[1], f[2], f[3]};
	f[0] = (f_temp[0] * f_temp[0] % 666013 + f_temp[1] * f_temp[2] % 666013) % 666013;
	f[1] = (f_temp[0] * f_temp[1] % 666013 + f_temp[1] * f_temp[3] % 666013) % 666013;
	f[2] = (f_temp[2] * f_temp[0] % 666013 + f_temp[3] * f_temp[2] % 666013) % 666013;
	f[3] = (f_temp[2] * f_temp[1] % 666013 + f_temp[3] * f_temp[3] % 666013) % 666013;
	pow(f, n, curr_step + 1);

	if (n & (1<<curr_step)) {
        long long f_temp2[] = {f[0], f[1], f[2], f[3]};
		f[0] = (f_temp2[0] * f_temp[0] % 666013 + f_temp2[1] * f_temp[2] % 666013) % 666013;
		f[1] = (f_temp2[0] * f_temp[1] % 666013 + f_temp2[1] * f_temp[3] % 666013) % 666013;
		f[2] = (f_temp2[2] * f_temp[0] % 666013 + f_temp2[3] * f_temp[2] % 666013) % 666013;
		f[3] = (f_temp2[2] * f_temp[1] % 666013 + f_temp2[3] * f_temp[3] % 666013) % 666013;
	}
}



int main() {
	freopen("kfib.in", "r", stdin);
	freopen("kfib.out", "w", stdout);

	int n;
	scanf("%d", &n);

	long long f[] = {0, 1, 1, 1};
	pow(f, n-1, 0);

	printf("%lld\n", f[3] % 666013);
	return 0;

}