Below, a pair \((a_i, b_i)\) is called effective when it causes a swap in at least one of your permutations, and the application of a swap caused by an effective pair to the permutation tuple is called an effective swap.
The following fact can be proved.

Proposition: During the \(M\) operations, there can be at most \(N(N-1)/2\) effective swaps.

(Proof) Let \(X\) be the number of ineffective integer pairs \((a, b)\) for your permutations. Initially, \(X=0\). One can prove the following lemma on \(X\).

Lemma: Each effective swap increases \(X\) by \(1\) or more.

(Proof of lemma) When an effective pair \((a, b)\) is applied to the permutation tuple, \((a, b)\) becomes ineffective, increasing the contribution of \((a, b)\) to \(X\) by \(1\).
Of the contributions of other integer pairs, those of the following two types of integer pairs may decrease.

• \((c, a)\) was ineffective but made effective by the \((a, b)\) swap.
• \((b, c)\) was ineffective but made effective by the \((a, b)\) swap.

Consider the former case. The ineffectiveness of \((c, a)\) means that \(p_c \leq p_a\) holds for all your permutations \(p\). Applying the \((a, b)\) swap is equivalent to replacing \(p_a, p_b\) with \(\min(p_a, p_b), \max(p_a, p_b)\), so from \(p_c \leq p_a \leq \max(p_a, p_b)\), the permutation \(p'\) after the swap satisfies \(p'_c ≤ p'_b\), so \((c, b)\) is ineffective after the swap.
Additionally, if \((c, a)\) was ineffective but made effective by the (a, b) swap, there is a permutation \(p\) such that \((p_c, p_a, p_b) = (1, 1, 0)\). Therefore, in this case, \((c, b)\) was an effective swap before the swap.
Thus, it has been shown that when the contribution of \((c, a)\) to \(X\) decreases, that of \((c, b)\) increases by \(1\), canceling the negative contribution to \(X\).
The same argument applies to the latter case. Therefore, each effective swap increases \(X\) by \(1\) or more. (End of proof of lemma)

We have \(X = N(N-1)/2\) when all permutations are sorted, so combining this with the lemma proves there can be at most \(N(N-1)/2\) effective swaps. (End of proof)

One can use this fact to see that a naive DP with appropriate pruning can work quickly.
Let us explain in detail. The number of sorted permutations at some time can be computed as follows if one knows the set of binary sequences of length \(N\) that will be sorted when the swaps so far are applied.

• Consider an \(N\)-dimensional grid with \(2 \times 2 \times \dots \times 2\) cells, where the cells at the coordinates corresponding to the binary sequences that will be sorted by applying the swaps are passable, and the other cells are impassable. Then, the number of paths from \((0,0, \dots ,0)\) to \((1,1, \dots,1)\) corresponds to the number of permutations that are sorted.

The above path-counting DP works in \(\mathrm{O}(N 2^N)\) time, so combining this with the fact that there are \(\mathrm{O}(N^2)\) updates on the set of binary sequences that will be sorted, this DP part of the solution to compute the number of sorted permutations only takes \(\mathrm{O}(2^N N^3)\) time in total.

Now, consider a DP to manage the state when applying swaps to a binary sequence of length \(N\). We define an array \(S\) of length \(2^N\) and a two-dimensional array \(C\) of size \(N \times N\) as follows:

• Sx:= (the state after applying \((a, b)\) to the state \(x\))
• C[i][j]: (the number of \(S[x]\) whose \(i\)-th bit is \(1\) and the \(j\)-th bit is \(0\), where \(i < j\))

When applying \((i, j)\) swap, perform the following steps.

1. Check whether \(C[i][j]\) is non-zero to determine whether \((i, j)\) swap is effective in \(O(1)\) time. If it is not effective, abort the process.
2. If necessary, scan all \(S[x]\) and update them by swapping the \(i\)-th and \(j\)-th bits of \(S[x]\) when they are swappable.
   • Accordingly, update the value of \(\mathrm{O}(1)\) at the same time. Since you only need to do this for parts \(C[i][*], C[j][*], C[*][i], C[*][j]\), it can be done in \(\mathrm{O}(N)\) time.
   • If S[x] is now sorted, set the cell corresponding to \(x\) as passable.
3. Then, perform the path-counting DP and update the answer.

This algorithm works in \(\mathrm{O}(2^N N^3 + M)\) time in total, which is fast. Sample Implementation
There is also an easier-to-implement \(\mathrm{O}(2^N N^4 + M)\) solution, which is sufficient for getting AC. Sample Implementation

Thus, this problem can be solved in \(\mathrm{O}(2^N N^4 + M)\) or \(\mathrm{O}(2^N N^3 + M)\) time, which is fast enough.

(There is also a \(\mathrm{O}^\ast (3^N)\) solution that updates the table for the path-counting DP each time there is a new passable cell, using the fact that there are at most \(\mathrm{O}(2^N N^2)\) adjacent swaps on binary sequences in total.)