#include <iostream>
#include <string.h>
using namespace std;

int Fibonacci[2][2]={1,1,1,0};

void matrix_pow(int c[2][2],int n){

	int i,j,k;
	if(n == 1){
		memcpy(c,Fibonacci,4 * sizeof(int));
		return;
	}
	int tmp[2][2];
	matrix_pow(tmp,n/2);
	for(i = 0;i < 2;i++)
		for(j = 0;j < 2;j++){
			c[i][j] = 0;
			for(k = 0;k < 2;k++)
				c[i][j] = (c[i][j] + tmp[i][k] * tmp[k][j]) % 10000;
		}

	//指数为奇数
	if(n & 1){								
		memcpy(tmp,c,4 * sizeof(int));
		for(i = 0;i < 2;i++)
			for(j = 0;j < 2;j++){
				c[i][j] = 0;
				for(k = 0;k < 2;k++)
					c[i][j] = (c[i][j] + tmp[i][k] * Fibonacci[k][j]) % 10000;
			}
	}
}
int main(){
	int n;
	while(cin>>n && n >= 0){
		if(n == 0){
			cout<<0<<endl;
			continue;
		}
		if(n == 1 || n == 2){
			cout<<1<<endl;
			continue;
		}
		n-=2;
		int c[2][2];
		matrix_pow(c,n);
		cout<<(c[0][0] + c[1][0]) % 10000<<endl;

	}
	return 0;
}