「行swapしか出来ない場合の答え」 × 「列swapしか出来ない場合の答え」がこの問題の答えになります。これは、列swapをしても、行swapの条件に一切影響がないことからわかります。

「行swapしか出来ない場合の答え」を考えます。

swap可能な行ベクトルの間に辺を張った時に、連結なベクトル同士は好きにswap出来ることがわかります。

例えば A - B - C - D で A, Dをswapしたいならば

A - B - C - D
-> B - A - C - D
-> B - C - A - D
-> B - C - D - A
-> B - D - C - A
-> D - B - C - A

と言った具合です。

よって、連結成分ごとに (連結成分のサイズ)! を求め、これを全てかけたものが答えです。例えばatcoder/dsuを実装に使う事ができます。