用矩阵快速幂转化，最后返回的是左上角的数。

/*#include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

using namespace std;
const int MOD = 1e5;
void mul(int a[][2],int b[][2])
{
int 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] +a[i][j] *b[k][j])%MOD;
memcpy(a,c,sizeof c);//把c数组复制到a
}
int fib(int n){
int a[2][2] = {0,1,0,0};
int f[2][2] = {0,1,1,1};
while(n){
if(n &1) mul(a,f);
mul(f,f);
n>>=1;
}
return a[0];
}

int main()
{
int n;
while(cin>>n,n!= -1)
cout<<fib(n)<<endl;

return 0;

}
*/