Fibonacci

定义如下：
    F(0) = 0 ,F(1) = 1;
    f(n) = F(n-1)+F(n-2)

1性质一：模除周期性

数列的数模除某个数的结果会呈现一定周期性，因为数列中的某个数取决与前两个数，一旦有连着的两个数的模除结果分别等于第0 第一项的模除结果，那麽代表着一个新的周期的的开始，如果模除n，则每个周期中的元素不会超过n×n;

性质二：黄金分割

随着i的增大F(n) / F(n-1) 接近于0.618

性质三：平方与前后项

从第二项开始，每个奇数项的平方都比前后两项之积多一，每个偶数项的平方比前后两项之积少一.

性质四：

斐波那契数列的第n+2项代表了集合{1，2，...n}中所有不包含相邻正整数的子集的个数.

性质五：求和

F1 + F3 +F5 +F7 ....+F(2*n-1)  =  F(2n) - F(2) + F(1)

F2 + F4 + F6 + F8 +...+F(2n) = F(2n+1) - F(1)

F1^2 + F2^2 + F3^2 + F4^2 + ... +Fn^2 = F(n)*F(n-1)

性质六：两倍项关系

F(2n) / F(n) = F(n-1) + F(n+1)

性质七：尾数循环

个位数：周期60

最后两位：300

最后三位：1500

其他：
F(n-1) * F(n+1) - F(n)^2 = (-1)^n

F(1) + 2F(2) + 3F(3) + ... + nF(n) = nF(n+2) - F(n+3) +2

double po(double a,int n)
{
    for(int i =1;i<=n;++i)
        a*=a;
    return a;
}
double solve1(int n)
{
    return 1/sqrt(5)*(po(((1+sqrt(5))/2),n)-po(((1-sqrt(5))/2),n));
}

ll solve3(ll n)
{
    if(n==0)
        return 0;
    else if(n==1||n==2)
        return 1;
    else
    {
        return solve3(n-1)+solve3(n-2);
    }
    
}

ll solve2(ll n)
{
    F[0] = 0;
    F[1] = 1;
    F[2] = 1;
    if(n==1||n==0||n==2)
        return F[n];
    else
    {
        for(ll i =3;i<=n;++i)
        {
            F[i] = F[i-1]+ F[i-2];
        }
        return F[n];
    }
}

ll solve4(ll n)
{
    //分治
    if(n == 0)
        return 0;
    if(n==1||n==2)
        return 1;
    
    ll first = 0;
    ll second = 1;
    while(0 < n--)
    {
        second += first; 
        first = second - first; 
    }
    return first + second;

}

#include <iostream>
#include<cstring>
#include<stdio.h>
using namespace std;
typedef long long ll;
const int mod=10000;
int f=2;
struct node
{
	ll materix[5][5];
};

node mul(node a,node b)  //矩阵乘法 
{
	node res;
	memset(res.materix,0,sizeof res.materix);
	for(int i=1;i<=f;i++)
		for(int j=1;j<=f;j++)
			for(int k=1;k<=f;k++)
				res.materix[i][j]=(res.materix[i][j]+a.materix[i][k]*b.materix[k][j])%mod;
	return res;	
}

node ksm(node a,ll b)
{
	node ans;
	memset(ans.materix,0,sizeof ans.materix);
	for(int i=1;i<=f;i++)
		ans.materix[i][i]=1;
	while(b)
	{
		if(b&1)
			ans=mul(ans,a);
		b>>=1;
		a=mul(a,a);
	}
	return ans;
}

int main()
{
	ll N;
	while(cin>>N&&N!=-1)
	{
		if(N==1||N==2)
			printf("1\n");
		if(N==0)
			printf("0\n");
		else
		{
			node a,b;
			a.materix[1][1]=1; a.materix[1][2]=1;
			a.materix[2][1]=1; a.materix[2][2]=0;   //a是那个幂矩阵，
			b.materix[1][1]=1; b.materix[1][2]=0;
			b.materix[2][1]=1; b.materix[2][2]=0;   //b是最初始的矩阵
			node ans = ksm(a ,N-2);  
			ans = mul(ans ,b) ;
			printf("%d\n",ans.materix[1][1] ) ;
		}
	}
	return 0;
}