全ての列に対して1回ずつ操作することは、全ての行に対して1回ずつ操作することに 置き換えて良いです。従って、操作しない列があるとしても答えは変わりません。

行に対する操作を先に考えます。行に対する操作の結果、盤面の数字の最小値は m になったとします。
これは、操作しない列があることから最終的な盤面の数字の最小値でもあるので、m が異なれば異なる盤面になることが分かります。
このような操作方法は、

(Nm+1)H(Nm)H(N − m + 1)^H − (N − m)^H 通り

あります。

このそれぞれに対して、列に対する操作を考えます。
最小値が m であることから、意味のある操作は 00 回以上 (Nm)(N − m) 回以下です。
よって、操作しない列があるような操作方法は、全体から全ての列に対して1回以上操作する場合を引き算することで

(Nm+1)W(Nm)W(N − m + 1)^W − (N − m)^W 通り

と分かります。

以上より、答えは m=0N((Nm+1)H(Nm)H)×((Nm+1)W(Nm)W)\displaystyle \sum_{m=0}^{N} ((N − m + 1)^H − (N − m)^H)\times ((N − m + 1)^W − (N − m)^W) 通り

となります。繰り返し2乗法によって、これは O(N(logH+logW))O(N(\log H+\log W)) で求めることができます。