#include<stdio.h>
int juzhen[4];
void countou(int *a)
{
	int b[4],i;
	for(i=0;i<4;i++)
	{
	   b[i]=a[i];
	}
	a[0]=(b[0]*b[0]+b[1]*b[2])%10000;
	a[1]=(b[0]*b[1]+b[1]*b[3])%10000;
	a[2]=(b[2]*b[0]+b[3]*b[2])%10000;
	a[3]=(b[2]*b[1]+b[3]*b[3])%10000;
}
void countji(int *a)
{
	int b[4],i;
	for(i=0;i<4;i++)
	{
	   b[i]=a[i];
	}
	a[0]=(b[0]*b[0]+b[1]*b[2])%10000;
	a[1]=(b[0]*b[1]+b[1]*b[3])%10000;
	a[2]=(b[2]*b[0]+b[3]*b[2])%10000;
	a[3]=(b[2]*b[1]+b[3]*b[3])%10000;
	for(i=0;i<4;i++)
	{
	   b[i]=a[i];
	}
	a[0]=(b[0]+b[1])%10000;
	a[1]=(b[0])%10000;
	a[2]=(b[2]+b[3])%10000;
	a[3]=(b[2])%10000;
}
int main()
{
	int i,vist[100],number;
	__int64 n;

	for(;;)
	{
		scanf("%I64d",&n);
		if(n==0)
		{
			printf("0\n");
			continue;
		}
		if(n==-1)
			break;
		juzhen[0]=1;
		juzhen[1]=1;
		juzhen[2]=1;
		juzhen[3]=0;
		i=0;
		while(n/2!=0)
		{
           // w[i]=n;
			if(n%2==1)
			{
				vist[i]=1;
			}
			else
			{
				vist[i]=0;
			}
			n=n/2;
			i++;
		}
		number=i;
		/*for(i=0;i<number;i++)
		{
			printf("%d ",vist[i]);
		}*/
		//printf("\n");
	//	printf("--%d\n",number);
		for(i=number;i>0;i--)
		{
			if(vist[i-1]==0)
			{
				countou(juzhen);
			}
			if(vist[i-1]==1)
			{
				countji(juzhen);
			}
		}
	    printf("%d\n",juzhen[1]%10000);
	}
	return 0;
}