#include<bits/stdc++.h>
using namespace std;

int mul_inverse(int x){
	if(x<0){
		x= ((x%26)+26)%26;
	}
	for(int i=0; i<26; i++){
		if ((x*i)%26==1){
			return i;
		}
	}
	return -1;
}
int determinant(int** mat, int n){
	if(n==0){
		return 0;
	}
	if(n==1){
		return mat[0][0];
	}
	if (n==2){
		return mat[0][0]*mat[1][1]- mat[0][1]*mat[1][0];
	}
	int det=0;
	int** sub_mat= new int*[n-1];
	for(int i=0;i<n-1; i++){
		sub_mat[i]= new int[n-1];
	}
	for(int i=0; i<n; i++){
		int row=0, col;
		for(int j=1; j<n; j++){
			col=0;
			for(int k=0; k<n; k++){
				if (k==i){
					continue;
				}
				sub_mat[row][col]= mat[j][k];
				col++;
			}
			row++;
		}
		det+= pow(-1, i)* mat[0][i]* determinant(sub_mat, n-1);
	}
	for(int i=0; i<n-1; i++){
		delete [] sub_mat[i];
	}
	delete [] sub_mat;
	return det;
}
int cofactor(int** mat, int n, int r, int c){
	int** sub_mat= new int*[n-1];
	for(int i=0;i<n-1; i++){
		sub_mat[i]= new int[n-1];
	}
	int row=0, col;
	for(int i=0; i<n ; i++){
		if(i==r){
			continue;
		}
		col= 0;
		for(int j=0; j<n ;j++){
			if(j==c){
				continue;
			}
			sub_mat[row][col]= mat[i][j];
			col++;
		}
		row++;
	}
	int det= determinant(sub_mat, n-1);
	for(int i=0; i<n-1; i++){
		delete [] sub_mat[i];
	}
	delete [] sub_mat;
	return det;
}
int** inverse(int** mat, int n){
	int det= determinant(mat, n);
	int det_inv= mul_inverse(det);
	if(det_inv==-1){
		cout<<"Inverse of matrix does not exist\n";
		return NULL;
	}
	int** inv= new int*[n];
	for(int i=0;i<n; i++){
		inv[i]= new int[n];
	}
	for(int i=0; i<n; i++){
		for(int j=0; j<n ;j++){
			inv[j][i]= ((det_inv*(int)pow(-1, i+j)* cofactor(mat, n, i, j))%26+ 26)%26;
		}
	}
	return inv;
}
int** mat_mul(int** mat1, int** mat2, int m, int n){
	int** mat3= new int*[m];
	for(int i=0; i<m; i++){
		mat3[i]= new int[n];
		for(int j=0; j<n; j++){
			mat3[i][j]= 0;
		}
	}
	for(int i=0; i<m; i++){
		for(int j=0; j<n; j++){
			for(int k=0; k<n; k++){
				mat3[i][j]= (mat3[i][j]+ mat1[i][k]*mat2[k][j])%26;
			}
		}
	}
	return mat3;
}

string encrypt(string plain_text, int** key, int n){
	int sz= plain_text.size();
	int m= sz/n + (sz%n?1:0);
	int** p_mat= new int*[m];
	int count=0;
	for(int i=0; i<m ;i++){
		p_mat[i]= new int[n];
		for(int j=0; j<n; j++){
			if(count>=sz){
				p_mat[i][j]= 25;  //for z
				continue;
			}
			if (isupper(plain_text[count])){
				p_mat[i][j]= plain_text[count]-65;
			}else{
				p_mat[i][j]= plain_text[count]-97;
			}
			count++;
		}
	}
	int** c_mat= mat_mul(p_mat, key, m, n);
	count=0;
	string cipher_text="";
	for(int i=0; i<m ;i++){
		for(int j=0;j<n; j++){
			if (isupper(plain_text[count])){
				cipher_text+= char(c_mat[i][j]+65);
			}else{
				cipher_text+= char(c_mat[i][j]+97);
			}
			count++;
		}
	}
	for(int i=0; i<m; i++){
		delete [] c_mat[i];
		delete [] p_mat[i];
	}
	delete [] c_mat;
	delete [] p_mat;
	return cipher_text;
}

string decrypt(string cipher_text, int** key, int n, int p_sz){
	int** inv= inverse(key, n);
	if(inv== NULL){
		return "";
	}
	cout<<"Inverse of key is: \n";
	for(int i=0; i<n; i++){
		for(int j=0; j<n ;j++){
			cout<<inv[i][j]<<" ";
		}
		cout<<endl;
	}
	int sz= cipher_text.size();
	int m= sz/n + (sz%n?1:0);
	int** c_mat= new int*[m];
	int count=0;
	for(int i=0; i<m ;i++){
		c_mat[i]= new int[n];
		for(int j=0; j<n; j++){
			if(count>=sz){
				c_mat[i][j]= 25;  //for z
				continue;
			}
			if (isupper(cipher_text[count])){
				c_mat[i][j]= cipher_text[count]-65;
			}else{
				c_mat[i][j]= cipher_text[count]-97;
			}
			count++;
		}
	}
	int** p_mat= mat_mul(c_mat, inv, m, n);
	count=0;
	string plain_text="";
	for(int i=0; i<m ;i++){
		for(int j=0;j<n; j++){
			if(count>=p_sz){
				break;
			}
			if (isupper(cipher_text[count])){
				plain_text+= char(p_mat[i][j]+65);
			}else{
				plain_text+= char(p_mat[i][j]+97);
			}
			count++;
		}
	}
	for(int i=0; i<m; i++){
		delete [] c_mat[i];
		delete [] p_mat[i];
	}
	for(int i=0; i<n; i++){
		delete [] inv[i];
	}
	delete [] inv;
	delete [] c_mat;
	delete [] p_mat;
	return plain_text;
}

int main(){
	string plain_text;
	cout<<"Enter plain text: ";
	getline(cin, plain_text);
	int n;
	cout<<"Enter key size: ";
	cin>>n;
	cout<<"Enter key: \n";
	int** mat= new int*[n];
	for(int i=0;i<n; i++){
		mat[i]= new int[n];
	}
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			cin>>mat[i][j];
		}
	}

	cout<<"\nEncryption:\n";
	string cipher_text= encrypt(plain_text, mat, n);
	cout<<"Cipher: "<<cipher_text<<endl;

	cout<<"\nDecryption:\n";
	string p_text= decrypt(cipher_text, mat, n, plain_text.size());
	cout<<"Plain Text: "<<p_text<<endl;
	for(int i=0; i<n; i++){
		delete [] mat[i];
	}
	delete [] mat;
}