令 $\{B_{ij}\}$ 为 $\{A_{ij}\}$ 的二维前缀和，即 $B_{ij}=\bigoplus_{x=1}^i\bigoplus_{y=1}^j A_{xy}$。容易发现 $A$ 和 $B$ 一一对应。

限制条件可以转化为 $B_{xy}=1$ 和 $B_{xM}\oplus B_{Ny}\bigoplus B_{NM}=0$。注意因为 $x,y< N$，两类限制互不相交。对于第一类限制，我们只需要数有多少对不同的 $(x,y)$。对于第二类限制，我们可以枚举 $B_{NM}$ 后，转化为在 $(x,M)$ 和 $(N,y)$ 之间连一条边权为 $B_{NM}$ 的边，然后判断是否为二分图，如果是则答案取决于连通块数量。时间复杂度 $O(K\log K)$。