/*
fibonacci数列对10000取余，30000一个周期;
fibonacci数列对100000取余，150000一个周期;
*/
#include<stdio.h>
#define MMP 30000
int f[MMP];
int main()
{
	int i;
	f[0] = 0; f[1] = 1;
	for(i = 2;i <=MMP; i++)/*<= 之间不能有空格 */ 
	{
		f[i] = (f[i-1] +f[i-2])%10000;
	}
	int n;
	while(scanf("%d",&n),n!=-1)
	{
		printf("%d\n",f[n%30000]);
	}
}