矩阵快速幂

for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
 		for(int k=1;k<=n;k++)
 			c[i][j]+=a[i][k]*b[k][j];

ll pow_ksm(ll a,ll n)
{
	ll res = 1;
    while(n)
    {
        if(n&1) res = res*a%mod;
        a = a*a%mod;
        n>>=1;
    }
    return res;
}

struct matrix
{
    ll m[101][101];
}
matrix a, b;
matrix mul(matrix x,matrix y)
{
    matrix c;
    for(int i =1;i<=n;++i)
    {
        for(int j =1;j<=n;++j)
        {
            c.m[i][j] = 0;
		}
    }
    for(int i =1;i<=n;++i)
    {
        for(int j =1;j<=n;++j)
        {
            for(int k =1;k<=n;++k)
            {
                c.m[i][j] += x.m[i][k]*y.m[k][j]%mod;
            }
        }
    }
    return c;
}
matrix pow_ksm(matrix x,ll y)
{
    matrix ans;
  	memset(ans.m,0,sizeof ans.m);
	for(int i=1;i<=n;i++)
		ans.m[i][i]=1;
    while(y)
    {
        if(y&1) ans = mul(ans,x);
        x = mul(x,x);
        y>>=1;
    }
    return ans;
}

#include<iostream>

#include<cstring>
#include<stdio.h>
using namespace std;

typedef long long ll;
const int mod = 10000;
struct node
{
    ll m[5][5];
};
node mul(node a,node b)
{
    node c;
    memset(c.m,0,sizeof c.m);
    // for(int i =1;i<=5;++i)
    // {
    //     for(int j =1;j<=5;++j)
    //     {
    //         c.m[i][j] = 0;
    //     }
    // }
    for(int i=1;i<=2;++i)
    {
        for(int j =1;j<=2;++j)
        {
            for(int k =1;k<=2;++k)
            {
                c.m[i][j] =(c.m[i][j] + a.m[i][k]*b.m[k][j])%mod;
            }
        }
    }
    return c;
}
node ksm(node x,ll y)
{
    node ans;
    memset(ans.m,0,sizeof(ans.m));
    for(int i =1;i<=2;++i)
    {
        //for(int j =1;j<=2;++j)
            ans.m[i][i] = 1;
        
    }
    while(y)
    {
        if(y&1) ans = mul(ans,x);
        y>>=1;
        x = mul(x,x);
    }
    return ans;
}
int main()
{
    ll n;
    while(cin>>n&&n!=-1)
    {
        if(n==0)
            printf("0\n");
        else if(n==1||n==2)
            printf("1\n");
        else
        {
            node a,b;
            a.m[1][1] = 1;
            a.m[1][2] = 1;
            a.m[2][1] = 1;
            a.m[2][2] = 0;
            b.m[1][1] = 1;
            b.m[1][2] = 1;
            b.m[2][1] = 1;
            b.m[2][1] = 0;
            node ans = ksm(a,n-1);
            ans = mul(ans,b);
            printf("%d\n",ans.m[1][1] ) ;
         }
        
    }
    return 0;
}