int mod;
struct matrix
{
long long a[102][102];//根据实际数据局范围调整。
int r;
int c;
matrix mul (matrix x,matrix y)//矩阵相乘
{
matrix t;
t.r=x.r;
t.c=y.c;
for(int i=0; i<x.r; ++i)
for(int j=0; j<y.c; ++j)
{
t.a[i][j]=0;
for(int k=0; k<y.r; ++k)
t.a[i][j]=(t.a[i][j]+x.a[i][k]*y.a[k][j]%mod)%mod;
}
return t;
}
matrix pow (matrix x,int y)
{
matrix t=x;//快速幂肯定是方阵，x.r==x.c。所以直接让t=x，再将t中数组a转化成一个单位矩阵。
memset(t.a,0,sizeof(t.a));
for(int i=0; i<x.r; ++i) t.a[i][i] = 1;
while(y)//跟快速幂原理相同
{
if(y&1)
t=mul(t,x);
y/=2;
x=mul(x,x);
}
return t;
}
};
