解题思路：

分析斐波那契数列，我们容易得出这样一个结论：

2 x 2的矩阵{F(n+1), F(n) ; F(n), F(n-1)} = {F(n), F(n-1) ; F(n-1), F(n-2)} *{1, 1 ; 1, 0}

而{F(2), F(1) ; F(1), F(0)} = {1, 1 ; 1, 0}，所以可以得出{F(n+1), F(n) ; F(n), F(n-1)} ={1,1; 1,0}的n-1次方。然后我们可以用分治法很容易的十分求解。

C++程序代码如下：

#include <map>
#include <iostream>
#include <vector>

#define LEN sizeof(matrix)
using namespace std;

struct matrix
{
 long a, b, c, d;
};

matrix e = {1, 1, 1, 0};

long getRemainder(const long &d1,const int &d2)
{
 long temp=(long)d1/d2;
 return d1-temp*d2;
}

matrix* matrixMultiple(matrix *m, matrix *n)
{
 matrix *out = (matrix*)malloc(LEN);
 out->a = m->a * n->a + m->b * n->c;
 out->b = m->a * n->b + m->b * n->d;
 out->c = m->c * n->a + m->d * n->c;
 out->d = m->c * n->b + m->d * n->d;
 if (out->a > 10000)
  out->a = getRemainder(out->a, 10000);
 if (out->b > 10000)
  out->b = getRemainder(out->b, 10000);
 if (out->c > 10000)
  out->c = getRemainder(out->c, 10000);
 if (out->d > 10000)
  out->d = getRemainder(out->d, 10000);
 if (m != &e)
  free(m);

 return out;
}

matrix* divideCompute(long n)
{
 matrix *temp = NULL;
 //temp = (matrix*)malloc(LEN);
 if (n == 1)
  return &e;
 else if (getRemainder(n, 2) == 0)
 {
  temp = divideCompute(n/2);
  return matrixMultiple(temp, temp);
 }
 else
 {
  temp = divideCompute(n/2);
  return matrixMultiple(matrixMultiple(temp,temp), &e);
 }
}

int main()
{
 vector<long> input;
 long value;
 while (cin >> value)
 {
  if (value == -1)
   break;
  input.push_back(value);
 }
 vector<long>::iterator it;
 for (it = input.begin(); it != input.end(); ++it)
 {
  long n = *it;
  if (n == 0)
   cout<<0<<endl;
  else
   cout<<getRemainder(divideCompute(n)->b, 10000)<<endl;
 }
 
 return 0;
}