int n = 100;
int minRange = 0;
int maxRange = 1000000000;

LIB "poly.lib";
ring r = 0, x, dp;
int i, j;
poly zero = 0;
poly mlt, p, ratio;
matrix m[n][n];

proc generateMatrix() {
	for(i = 1; i <= n; i++) {
		for(j = 1; j <= n;  j++) {
			m[i, j] = random(minRange, maxRange);
		}
	}
}

proc getDiagonal() {
	poly res = 1;
	for(i = 1; i <= n; i++)  {
		res = res * m[i, i];
	}
	return(res[1][1] / ratio);
}

proc getNotZero(int cl) {
	for(i = cl; i <= n; i++) {
		if(m[i, cl] != zero) {
			return(i);
		}
	}
	return(-1);
}

proc changeRow(int first, int second) {
	poly tmp;
	for(i = first; i <= n; i++) {
		tmp = m[first, i];
		m[first, i] = m[second, i];
		m[second, i] = tmp;
	}
}

proc getLCM(int col) {
	int res = 1;
	for(i = col; i <= n; i++) {
		res = lcm(res, int(m[i, col]));
	}
	return(res);
}

proc gaussMatrix() {
	int i, j, col, row;
	ratio = 1;
	mlt = 1; 
	p = 1;
	for(col = 1; col <= n; col++) {
		row = getNotZero(col);
		if(row == -1) {
			ratio = 0;
			return;
		} else {
			if(col != row) {
				changeRow(col, row);
				ratio = ratio * (-1);
			}
			mlt = getLCM(col);
			p = mlt / m[col, col];
			ratio = ratio * p;
			m = multrow(m, col, p);
			for(j = col + 1; j <= n; j++) {
				if(m[j, col] != zero) {
					p = mlt / m[j, col];
					ratio = ratio * p;
						for(i = col; i <= n; i++) {
						m[j, i] = m[j, i] * p - m[col, i];
					}
				} 
			}
		}
	}
}

proc solve() {
	gaussMatrix();
	if(ratio == 0) {
		return(0);
	} else {
		return(getDiagonal());
	}
}


generateMatrix();
det(m);
solve();
exit;