For each \(k\) \((1 \le k \le NM)\), we compute the number of ways in which \(k\) is never chosen. This value is \(\prod_{i=1}^{M} (N - \text{the number of occurrences of } k \text{ in } A_i)\).

For a fixed \(i\), computing “the number of occurrences of \(k\) in \(A_i\)” for all \(k\) \((1 \le k \le NM)\) takes \(\mathrm{O}(NM)\) time.

Thus, the problem can be solved in a total of \(\mathrm{O}(N^2M)\) time.