In fact, it is sufficient to know the number of distinct values in the sequence without explicitly tracking the mex.

We apply DP. Let \(\mathrm{dp}[i][j]\) be the number of valid configurations for \((A_1,A_2,\ldots,A_i)\) such that the number of different values appearing in \(A_1,A_2,\ldots,A_i\) is \(j\).

We will explain the transitions for the cases when \(S_i=1\) and when \(S_i=0\).

If \(S_i=1\), then \(A_i\) is uniquely determined, and it will always be between \(0\) and \(M\) if the current number of distinct values is at most \(M\). If the current number of different values is \(M+1\), then \(A_i=M+1\), and this transition is impossible.

From the above, the DP transition is as follows:

• For \(j=0,1,\ldots,M\), add \(\mathrm{dp}[i][j]\) to \(\mathrm{dp}[i+1][j+1]\).

If \(S_i=0\), there are cases where the number of distinct values increases and cases where it does not.

When the number of different values increases, there are \(M-j\) possibilities for \(A_i\). On the other hand, when the number of different values does not increase, there are \(j\) possibilities for \(A_i\).

From the above, the DP transition is as follows:

• For \(j=0,1,\ldots,M-1\), add \(\mathrm{dp}[i][j]\times(M-j)\) to \(\mathrm{dp}[i+1][j+1]\).

• For \(j=1,\ldots,M+1\), add \(\mathrm{dp}[i][j]\times j\) to \(\mathrm{dp}[i+1][j]\).

Since the number of different values appearing in \(A\) is at most \(N\), the DP table only has to be of size \(O(N\min(N,M))\). Thus, this problem can be solved in \(O(N\min(N,M))\).

As an aside: By observing the transitions or upon a bit of contemplation, one can see that when \(M\geq N-1\) and \(N\geq 2\), the answer is \(M^c\), where \(c\) is the number of zeros in \(S\).