奶牛家族

// 递推 f(n) = f(n-1)+f(n-3);

 class Mad{
 
 long[][] ad = new long[3][3];
 
}

public class Cows {
 
 int mod =1000000007;
 
 
 
 
 public Mad muti(Mad a,Mad b){
  
  long temp=0;
  
  Mad res = new Mad();
  
  for(int i=0;i<3;i++){
   for(int j=0;j<3;j++){
    for(int k=0;k<3;k++){
     
    // if(a.ad[i][k]>mod){a.ad[i][k]=a.ad[i][k]%mod;}
    // if(b.ad[k][j]>mod){b.ad[k][j]=b.ad[k][j]%mod;}
     
     temp += (a.ad[i][k]*b.ad[k][j])%mod;
     
     if(temp>mod){temp=temp%mod;}
  
    }
    
    res.ad[i][j] = temp;
    temp =0;
   }
  }
  
  return res;
  
 }
 
 public int countSum(int n){
  
  if(n==1){return 1;}
  if(n==2){return 2;}
  if(n==3){return 3;}
  
  int b = n-3;
  
  Mad res = new Mad();
  
  res.ad[0][0]=1;
  res.ad[1][1]=1;
  res.ad[2][2]=1;
  
  Mad a = new Mad();
  
  a.ad[0][0]=1;
  a.ad[0][2]=1;
  a.ad[1][0]=1;
  a.ad[2][1]=1;
  
  
  while(b>0){
   
   if((b&1)==1){
    
    res = muti(a,res); 
   }
   b>>=1;
   
   a = muti(a,a);
   
  }
  
  return (int)((3*res.ad[0][0]+2*res.ad[0][1]+res.ad[0][2])%mod);
  
  
  
 }

}