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

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

const int MOD = 666013;

struct Matrix {
	int a[2][2];
	Matrix() {
		a[0][0] = a[0][1] = 0;
		a[1][0] = a[1][1] = 0;
	}

	Matrix operator *(const Matrix &other) {
		Matrix res;
		for(int i = 0; i < 2; i++)
			for(int j = 0; j < 2; j++)
				for(int k = 0; k < 2; k++)
					res.a[i][j] = (res.a[i][j] + 1LL * a[i][k] * other.a[k][j]) % MOD;
		return res;
	}
};

Matrix pwr(Matrix M, int n) {
	Matrix res;
	res.a[0][0] = res.a[1][1] = 1;

	while(n != 0) {
		if(n % 2 == 1)
			res = res * M;
		M = M * M;
		n /= 2;
	}
	return res;
}

int main() {
	int n;
	fin >> n;

	Matrix M;
	M.a[0][0] = M.a[0][1] = M.a[1][0] = 1;

	fout << pwr(M, n).a[0][0] << '\n';

	return 0;
}