各 \(k(1 \le k \le NM)\) について、自分が \(1\) 回も選ばれないような方法の個数を求めればよいです。この値は \(\prod_{i=1}^{N} (M - A_i\) に含まれる \(k\) の個数 \()\) です。

\(i\) を固定したとき、全ての \(k(1 \le k \le NM)\) について「\(M - A_i\) に含まれる \(k\) の個数」を求めるのは \(\mathrm{O}(NM)\) で出来ます。

よって、全体で \(\mathrm{O}(N^2M)\) で解けます。