包除原理について考える

ABC172のE問題は次のような問題であった。

$1$ 以上 $M$ 以下の整数からなる長さ $N$ の数列 $A_1,A_2,\ldots ,A_N$ と $B_1,B_2,\ldots,B_N$ の組であって、以下の条件をすべて満たすものの個数を求めてください。

$1\leq i\leq N$ なる任意の $i$ について $A_i\neq B_i$

$1 \leq i < j \leq N$ なる任意の $(i,j)$ について $A_i\neq A_j$ かつ $B_i\neq B_j$

ただし、答えは非常に大きくなる可能性があるので、 $(10^9+7)$ で割ったあまりを出力してください。

この問題を考えてみたが煮詰まってしまい、泣きながら解答を見ると包除原理を利用した解法が載っていた。
解答には大まかに以下のような説明が載っていた。

各要素が $1$ 以上 $N$ 以下の整数である集合 $S$ について「 $i \in S$ なる全ての $i$ について $A_i = B_i$ 」が成り立つ $A,B$ の組の個数は ${}_M P_{|S|}\times \left( {}_{M-|S|}P_{N-|S|}\right)^2$ である。
包除原理より、上の個数に $(-1)^{|S|}$ をかけた $(-1)^{|S|}\times {}_M P_{|S|}\times \left( {}_{M-|S|}P_{N-|S|}\right)^2$ の全ての $S$ に対して総和をとったものが答えになる。

止まりなさい。完全にスピード違反である。

私の知っている包除原理は次のようなものである。

集合 $X_i\,(i=1,\ldots n)$ の和集合の元の個数は以下で表される。
$\begin{align*} \left|\bigcup_{i=1}^n X_i\right|&=\sum_{i}|X_i|-\sum_{i < j}\left|X_i\cap X_j\right| +\cdots + (-1)^{n-1}\left|X_1\cap \cdots \cap X_n\right|\\ &=\sum_{I \subset \{1,2,\ldots , n\},I\neq \varnothing} (-1)^{|I|-1} \left|\bigcap_{i \in I} X_i\right| \end{align*}$

包除原理をこの問題に対応させてみる。
$X_S$ を「 $i\in S$ なる $i$ 全てについて $A_i=B_i$ が成り立つ $A,B$ の組の集合」として定義する。
このとき $S_1,S_2 \subset \{1,2,\ldots ,N\}$ について $S_1\cap S_2=S$ が成り立つとき、 $X_{S_1}\cap X_{S_2} =X_{S}$ も成り立つ。
ここで、「 $1 \leq i \leq N$ に少なくとも一つ $A_i=B_i$ を満たす $i$ が存在する」ような $A,B$ の組の個数を考えると、それは上の包除定理の式にあてはめて、以下のように表せる。
$\begin{align*} \left|\bigcup_{|S|=1} X_S\right|&=\left|\bigcup_{i=1}^N X_{\{i\}}\right|\\ &=\sum_{I\subset \{1,2,\ldots ,N\},I\neq \varnothing} (-1)^{|I|-1} \left|\bigcap_{i\in I} X_{\{i\}}\right|\\ &=\sum_{S\subset\{1,2,\ldots ,N\},S\neq \varnothing} (-1)^{|S|-1} |X_S| & \left(\because \bigcap_{i\in S} X_{\{i\}} =X_S\right) \end{align*}$

ここで、「 $1 \leq i \leq N$ なる全ての $i$ で $A_i\neq B_i$ が成り立つ」ような $A,B$ の組の集合は上で考えた集合の補集合になっている。よって、今計算した結果を用いて答えを求められそうだ。
全体集合の元の個数は $|X_\varnothing|$ ( $A,B$ の並べ方になんの制約もないときの組の個数)と表せるので、求める個数は
$\begin{align*} \left|X_\varnothing \right|-\left|\bigcup_{|S|=1} X_S\right|&=\left|X_\varnothing \right|+\sum_{S\subset\{1,2,\ldots ,N\},S\neq \varnothing} (-1)^{|S|} |X_S|\\ &=\sum_{S\subset\{1,2,\ldots ,N\}} (-1)^{|S|} |X_S| \end{align*}$