第一次写矩阵的题目，第一次写快速幂的题目，第一次进行移位操作，第一次进行按位与操作

//#define LOCAL
#include <stdio.h>
#include <string.h>

#define MAXN 20 + 10

int n;
int a11, a12, a21, a22;
int b11, b12, b21, b22;
int c11, c12, c21, c22;
int d11, d12, d21, d22;

int main()
{
#ifdef LOCAL
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif
	while(~scanf("%d", &n) && n != -1)
	{
		// 数据初始化
	 	a11 = 1;
	 	a12 = 1;
	 	a21 = 1;
	 	a22 = 0;
	 	b11 = 1;
	 	b12 = 0;
	 	b21 = 0;
	 	b22 = 1;
		// 算法主体
		if(n == 0)
		{
			printf("0\n");
			continue;
		}
			
		while(n)
		{
			if(n & 1)
			{
				c11 = (a11 * b11 + a12 * b21) % 10000;
				c12 = (a11 * b12 + a12 * b22) % 10000;
				c21 = (a21 * b11 + a22 * b21) % 10000;
				c22 = (a21 * b12 + a22 * b22) % 10000;
				b11 = c11;
				b12 = c12;
				b21 = c21;
				b22 = c22;
			}
			d11 = (a11 * a11 + a12 * a21) % 10000;
			d12 = (a11 * a12 + a12 * a22) % 10000;
			d21 = (a21 * a11 + a22 * a21) % 10000;
			d22 = (a21 * a12 + a22 * a22) % 10000;
			a11 = d11;
			a12 = d12;
			a21 = d21;
			a22 = d22;
			n >>= 1; 
		}
	 	printf("%d\n", b12); 
	}
	return 0;
}