#include<iostream>
using namespace std;
int main()
{
 int n;
 bool fib[100];
 while(cin >> n) {
  if(n == -1) break;
  if(n == 0) {
   cout << 0 << endl;
   continue;
  }
  memset(fib, 0, sizeof(fib));
  int i = 0, j;
  int a = 1, b = 1, c = 1, d = 0;
  int temp_a, temp_b, temp_c, temp_d;
  while(n != 1) {
   if(n % 2 == 0) {
    n /= 2;
    fib[i ++] = 1;             //1记录相除
   }
   else {
    n --;
    fib[i ++] = 0;             //0记录相减
   }
  }
  for(j = i - 1; j >= 0; j --) {
   if(fib[j] == 1) {
    temp_a = (a * a + b * c) % 10000;
    temp_b = (a * b + b * d) % 10000;
    temp_c = (a * c + c * d) % 10000;
    temp_d = (c * b + d * d) % 10000;
    a = temp_a;
    b = temp_b;
    c = temp_c;
    d = temp_d;
   }
   else {
    temp_a = (a + b) % 10000;
    temp_b = a;
    temp_c = (c + d) % 10000;
    temp_d = c;
    a = temp_a;
    b = temp_b;
    c = temp_c;
    d = temp_d;
   }
  }
  cout << b << endl;
 }
 return 0;
}