C :

#include<stdio.h>  
const int  mode=10000;  
int main()  
{  
    int a[6],i,j,n,k=1;;  
    while(scanf("%d",&n)!=EOF)  
    {  
        if(n<1)printf("Case %d: 2\n",k++);  
        else  
        {  
            a[0]=2;  
            a[1]=a[2]=a[3]=a[4]=a[5]=0;  
            for(j=1;j<=n;j++)  
            {  
                for(i=5;i>0;i--)  
                    a[i]=a[i-1];  
                a[i]=(a[2]*3+a[3]*2+a[4])%mode;  
            }  
            printf("Case %d: %d\n",k++,(a[0]+a[1]+a[2]+a[3]+a[4]+a[5])%mode);  
        }  
  
    }  
  
    return 0;  
}  

C++ :

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
struct Matrix
{
    int s[6][6];
}h,p,a;
int m,T,ans,k; 
Matrix Mul(Matrix a,Matrix b)
{
    int i,j,k;
    Matrix h;
    memset(h.s,0,sizeof(h.s));
    for (k=0;k<6;k++)
      for (i=0;i<6;i++)
        for (j=0;j<6;j++)
           h.s[i][j]=(h.s[i][j]+a.s[i][k]*b.s[k][j])%10000;
    return h;
}
Matrix Mdata(int n)
{
    Matrix k;
    if (n==1) return h;
    k=Mdata(n/2);
    k=Mul(k,k);
    if (n%2) k=Mul(k,h);
    return k;
}
int main()
{ 
    T=0;
    memset(a.s,0,sizeof(a.s));
    a.s[5][0]=2;
    memset(h.s,0,sizeof(h.s));
    for (int i=0;i<6;i++) h.s[i][i+1]=1;
    h.s[5][2]=1; h.s[5][3]=2; h.s[5][4]=3;
    while (~scanf("%d",&m))
    {
         ans=0;
         k=6;
         while (k--)
         {
              if (m) p=Mul(Mdata(m),a); else p=a;
              ans+=p.s[5][0];
              if (!m) break;
              m--;
         }
         printf("Case %d: %d\n",++T,ans%10000);
    }
    return 0;
}