1 const int mo=1000000007; 2 int n; 3 int ksm(int x,int y) 4 { 5     int z=1; 6     while(y) 7     { 8         if(y&1)z=(1ll*x*z)%mo; 9         y>>=1; x=(1ll*x*x)%mo;10     }11     return z;12 }13 int t[301][601];14 struct matrix15 {16     int a[301][601];17     void cheng(matrix &b)    //矩阵乘法18     {19         for(int i=1;i<=n;i++)20         for(int j=1;j<=n;j++)21         {22             t[i][j]=0;23             for(int k=1;k<=n;k++)t[i][j]=(1ll*a[i][k]*b.a[k][j]+t[i][j])%mo;24         }25         for(int i=1;i<=n;i++)26         for(int j=1;j<=n;j++)a[i][j]=t[i][j];27     }28     void hswap(int i,int j)     //矩阵行交换29     {30         for(int k=1;k<=2*n;k++){ int t=a[i][k]; a[i][k]=a[j][k]; a[j][k]=t; }31     }32     void hadd(int i,int j,int l)     //矩阵行之间加减33     {34         for(int k=1;k<=2*n;k++)a[j][k]=(1ll*l*a[i][k]+a[j][k])%mo;35     }36     void qiuni()     //矩阵求逆37     {38         for(int i=1;i<=n;i++)a[i][i+n]=1;39         for(int i=1;i<=n;i++)40         {41             int j=i; while(a[j][i]==0)j++;42             if(i!=j)hswap(i,j);43             for(int j=i+1;j<=n;j++)if(a[j][i]!=0)44             {45                 int xx=(1ll*a[j][i]*ksm(a[i][i],mo-2))%mo;46                 hadd(i,j,(-xx)%mo);47             }48         }49         for(int i=n;i>=1;i--)50         {51             int xx=ksm(a[i][i],mo-2); hadd(i,i,(xx-1)%mo);52             for(int j=1;j<i;j++)if(a[j][i]!=0)hadd(i,j,(-a[j][i])%mo);53         }54         for(int i=1;i<=n;i++)55         for(int j=1;j<=n;j++){ a[i][j]=a[i][j+n]; a[i][j+n]=0; }56     }57     int det()     //求矩阵行列式58     {59         int ans=1;60         for(int i=1;i<=n;i++)61         for(int j=1;j<=n;j++)t[i][j]=a[i][j];62         for(int i=1;i<=n;i++)63         {64             int j=i; while(a[j][i]==0)j++;65             if(i!=j)hswap(i,j),ans=-ans;66             for(int j=i+1;j<=n;j++)if(a[j][i]!=0)67             {68                 int xx=(1ll*a[j][i]*ksm(a[i][i],mo-2))%mo;69                 hadd(i,j,(-xx)%mo);70             }71         }72         for(int i=1;i<=n;i++)ans=(1ll*ans*a[i][i])%mo;73         for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)a[i][j]=t[i][j];74         return ans;75     }76 };