実は mex を陽に管理しなくても，数列に含まれる値の種類数さえ分かれば十分です．

dp をします．\(\mathrm{dp}[i][j]=(A_1,A_2,\ldots,A_{i-1}\) の valid な決め方のうち 、\(A_1,A_2,\ldots,A_{i-1}\) に出現する値の種類数が \(j\) 個であるものの個数) と定義します．

\(S_i=1\) の場合と \(S_i=0\) の場合それぞれについて遷移を説明します．

\(S_i=1\) の場合，\(A_i\) は一意に定まり，現在の値の種類数が \(M\) 以下の場合必ず \(0\) 以上 \(M\) 以下です．現在の値の種類数が \(M+1\) の場合，\(A_i=M+1\) となり，この遷移はできません．

以上より dp の遷移は以下になります。

• \(j=0,1,\ldots,M\) について， \(\mathrm{dp}[i+1][j+1]\) に \(\mathrm{dp}[i][j]\) を加算する．

\(S_i=0\) の場合，\(A_i\) によって種類数が増える場合と増えない場合があります．

種類数が増える場合，\(A_i\) の候補は \(M-j\) 通りです．一方，種類数が増えない場合，\(A_i\) の候補は \(j\) 通りです．

以上より dp の遷移は以下になります。

• \(j=0,1,\ldots,M-1\) について， \(\mathrm{dp}[i+1][j+1]\) に \(\mathrm{dp}[i][j]\times(M-j)\) を加算する．

• \(j=1,\ldots,M+1\) について， \(\mathrm{dp}[i+1][j]\) に \(\mathrm{dp}[i][j]\times j\) を加算する．

\(A\) に出現する値の種類数は高々 \(N\) なので，dp テーブルは \(O(N\min(N,M))\) のサイズで十分です．よってこの問題を \(O(N\min(N,M))\) で解くことができました．

余談：遷移を観察するか少し考察すると，\(M\geq N-1\) かつ \(N\geq 2\) の場合，\(S\) に含まれる \(0\) の個数を \(c\) とすると答えは \(M^c\) であることが分かります．