考察

行列に $(0,1)$—ベクトルを掛けていくつかの行・列を取り出すことなどを考えると、問題は次のように言い換えられます。

$N \times M$ の $\mathbb{F}_2$ 行列 $A$ が与えられる。$vAw=1$ であるような行ベクトル $v \times \mathbb{F}_2^N$ と列ベクトル $w \in \mathbb{F}_2^M$ の組の個数を求めよ。

$vA=0$ の場合、条件を満たす $w$ は明らかに $0$ 個です。$vA\neq0$ の場合には、条件を満たす $w$ は全体の半分である $2^{M-1}$ 個になります（$vA$ のある非零成分の位置に対応する $w$ の成分は、それ以外を任意に決めると自動的に定まる）。

$r=\mathrm{rank} A$ とおくと、次元定理より $vA=0$ となる $v$ の個数は $2^{N-r}$ となり、答えは $(2^N-2^{N-r})2^{M-1}$ です。掃き出し法はこの方法が簡単です。

別解

無理やり関連させると、$vAw$ を考える代わりに $(vP^{-1})(PAQ)(Q^{-1}w)$ を考えてもよい、ということになりそう。