> #include <iostream>
> using namespace std;
> 
> const int num = 2;
> const int mod = 10000;
> 
> struct mat {
> 	int m[num][num];
> };
> 
> mat I{
> 	1,0,
> 	0,1
> };
> 
> mat mul(mat a, mat b) {
> 	mat ans;
> 	for(int i=0;i<num;i++)
> 		for (int j = 0; j < num; j++) {
> 			ans.m[i][j] = 0;
> 			for (int k = 0; k < num; k++)
> 				ans.m[i][j] += (a.m[i][k] * b.m[k][j]);
> 			ans.m[i][j] %= mod;
> 		}
> 	return ans;
> }
> 
> mat quick_pow(mat a, long long b) {
> 	mat ans = I;
> 	mat tmp = a;
> 	while (b > 0) {
> 		if (b & 1)
> 			ans = mul(ans, tmp);
> 		tmp = mul(tmp, tmp);
> 		b >>= 1;
> 	}
> 	return ans;
> }
> 
> int main() {
> 	long long n;
> 	mat a{
> 		1,1,
> 		1,0
> 	};
> 	while (cin >> n&&n!=-1) {
> 		mat tmp;
> 		tmp = quick_pow(a, n);
> 		cout << tmp.m[0][1] << endl;
> 	}
> 	return 0;
> }