矩阵快速幂-(斐波那契前n项平方和)

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#define LL long long
const LL mod=1e9+7;
using namespace std;
struct node{
    LL a[2][2];
    node(){
        memset(a,0,sizeof(a));  
    }
};
node Mul(node n1,node n2){
    node res;
    for(int i=0;i<2;i++)
      for(int j=0;j<2;j++)
       for(int k=0;k<2;k++){
          res.a[i][j]=(res.a[i][j]%mod+n1.a[i][k]*n2.a[k][j]%mod)%mod;
       }
    return res;
}
node solve(node n1,LL k){
    node res;
    for(int i=0;i<2;i++) res.a[i][i]=1;
    while(k){
        if(k&1) res=Mul(res,n1);
        k>>=1;
        n1=Mul(n1,n1);
    }
    return res;
}
int main(){
    LL n;
    cin>>n;
    node n1;  //矩阵初态
    n1.a[0][0]=1;
    n1.a[0][1]=1;
    n1.a[1][0]=1;
    n1.a[1][1]=0;
    node res=solve(n1,n-1);
    LL ans=((res.a[0][0]%mod+res.a[0][1]%mod)%mod*(res.a[1][0]%mod+res.a[1][1]%mod))%mod;
    cout<<ans;

    return 0;
}