#include <stdio.h> #include <string.h> long long n,mod=10000; void Matrix1(long long a[2],long long b[2][2]) { long long c[2]={0}; for(int j=0;j<2;j++) { for(int k=0;k<2;k++) { c[j]=(c[j]+a[k]*b[k][j]%mod)%mod; } } memcpy(a,c,sizeof(c)); } void Matrix2(long long b[2][2]) { long long c[2][2]={0}; for(int i=0;i<2;i++) { for(int j=0;j<2;j++) { for(int k=0;k<2;k++) { c[i][j]=(c[i][j]+b[i][k]*b[k][j]%mod)%mod; } } } memcpy(b,c,sizeof(c)); } int main() { while(~scanf("%lld",&n)) {
if(n==-1) break; else {
long long a[2]={0,1}; long long b[2][2]={0,1,1,1}; while(n) { if(n&1) Matrix1(a,b); Matrix2(b); n>>=1; } printf("%lld\n",a[0]); } } return 0; }