#include<stdio.h>
#define MAXN 100
int Num[MAXN];
int fabnaci(int n)
{
	int a=0;int b=1;int i=2;int c;
	if(n==0)
		return 0;
	if(n==1)
		return 1;
	while(i<=n)
	{
		c=(a+b)%10000;
		a=b;
		b=c;
		i++;
	}
	return c;
}
		
int main()
{
	int j=0,counter=0;
	do
	{
		scanf("%d",&Num[j]);
		if(Num[j]!=-1)
		{
			j++;
			counter++;
		}
		else
			break;
	}while(1);
	j=0;
	while(j<counter)
		printf("%d\n",fabnaci(Num[j++]));
	
	return 0;
}