#include<iostream>
using namespace std;
int main()
{
	int n;
	bool fib[100];
	while(cin >> n) {
		if(n == -1) break;
		if(n == 0) {
			cout << 0 << endl;
			continue;
		}
		memset(fib, 0, sizeof(fib));
		int i = 0, j;
		int a = 1, b = 1, c = 1, d = 0;
		int temp_a, temp_b, temp_c, temp_d;
		while(n != 1) {
			if(n % 2 == 0) {
				n /= 2;
				fib[i ++] = 1;             //1记录相除
			}
			else {
				n --;
				fib[i ++] = 0;             //0记录相减
			}
		}
		for(j = i - 1; j >= 0; j --) {
			if(fib[j] == 1) {
				temp_a = (a * a + b * c) % 10000;
				temp_b = (a * b + b * d) % 10000;
				temp_c = (a * c + c * d) % 10000;
				temp_d = (c * b + d * d) % 10000;
				a = temp_a;
				b = temp_b;
				c = temp_c;
				d = temp_d;
			}
			else {
				temp_a = (a + b) % 10000;
				temp_b = a;
				temp_c = (c + d) % 10000;
				temp_d = c;
				a = temp_a;
				b = temp_b;
				c = temp_c;
				d = temp_d;
			}
		}
		cout << b << endl;
	}
	return 0;
}