/*fibonacci数列对10000取余，30000一个周期;fibonacci数列对100000取余，150000一个周期;*/#include
     
      #define MMP 30000int 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]);	}}