#include <iostream>
using namespace std;

long long f[10000000] = { 0 };

long long fibo(long long num) {
	f[0] = 0; f[1] = 1; f[2] = 1;
	for (long long i = 3; i <= num; i++) {
		f[i] = f[i - 1]%1000000 + f[i - 2]%1000000;
	}
	return f[num];
}

int main() {
	long long n, m, temp;
	int i;
	cin >> n;
	temp = n % 1000000;
	if (temp == 0) {
		while (n > 1000000) {
			n /= 1000000;
		}
		m = fibo(n);
	}
	else {
		m = fibo(temp);
	}

	cout << m % 1000000 << '\n';
	return 0;
}