Orthogonal basis over \(\mathbb F_p\)
Work modulo \(p=1\,000\,000\,007\). Given an \(n\times m\) matrix whose rows
span a subspace (W\subseteq\mathbb F_p^m), output an orthogonal basis of
\(W\) for the standard dot product
\[
\langle x,y\rangle=\sum_i x_i y_i\pmod p.
\]
The test spaces are guaranteed to have an orthogonal basis. Any orthogonal
basis is accepted.
Input
The first line contains (n,m), followed by the (n) rows of the matrix.
Output
Print the dimension (r), followed by (r) independent vectors of length
(m). Each vector must lie in the row space, the vectors must span it, and
distinct vectors must have dot product zero modulo (p).
Constraints
- \(1\le n,m\le 100\)
- Every matrix entry is an integer in \([0,p)\)