Mex Permutation (Hard)

**This is the hard version of the problem. Here you need to count the number of valid permutations $P$. In the easy version, you need to construct any valid permutation. This version is worth $50$ points in Division $1$ and unscoreable in other Divisions.** Stack had a permutation $P$ of the integers $[0, N - 1]$. Based on that, he calculated an array $A$ of length $N$ as follows: - $A_i = \tex