/*
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]);
}
}
