struct Matrix{ int mat[maxn][maxn]; }; int n, k; Matrix Matrix_mul(Matrix a, Matrix b){ Matrix ret; memset(ret.mat, 0, sizeof(ret.mat)); for(int i = 1; i <= k; i++) for(int j = 1; j <= k; j++){ if(a.mat[i][j]){ for(int kk = 1; kk <= k; kk++) ret.mat[i][kk] += (a.mat[i][j]*b.mat[j][kk])%6; //ret.mat[i][k] %= 6; } } return ret; } Matrix Matrix_pow(Matrix tt, int nn){ Matrix ret; Matrix temp = tt; memset(ret.mat, 0, sizeof(ret.mat)); for(int i = 1; i<= k; i++) ret.mat[i][i] = 1; while(nn){ if(nn&1) ret = Matrix_mul(ret, temp); temp = Matrix_mul(temp, temp); nn >>= 1; } return ret; }