ヒント → https://atcoder.jp/contests/arc158/editorial/5901

---

[1] 条件の言い換え

手順を選んだ \(k\) の列 \(X = (k_1, \ldots, k_M)\) として表します．\(X\) が条件を満たすのはどのようなときかを整理しましょう．

安定ソートは同一の値の順序を変えないので，各 \(B_i\) がどの \(A_i\) 由来であるかは確定します．\(B_1, B_2, \ldots, B_N\) が目的の順序に並ぶことは，次と同値です：任意の \(i\) に対して，\(B_i\) よりも右側に \(B_{i+1}\) が並ぶ．

以下 \(B_i\), \(B_{i+1}\) の「位置関係」と書けば，どちらが左側・右側にあるのかを指すこととします．

\(i\) を固定して，\(2\) 数 \(B_i, B_{i+1}\) の位置関係のみに注目しましょう．\(B_i\) の \(10^k\) の位を \(a\)，\(B_{i+1}\) の \(10^k\) の位を \(b\) とするとき，各安定ソートによって \(B_i, B_{i+1}\) の位置関係は次のように変化します：

• \(a<b\) ならば \(B_i\) よりも右側に \(B_{i+1}\) が並ぶ．
• \(a=b\) ならば \(B_i, B_{i+1}\) の位置関係は変化しない．
• \(a>b\) ならば \(B_{i+1}\) よりも右側に \(B_i\) が並ぶ．

したがって，\(a<b\) が成り立つような \(k\) 全体の集合を \(S\) とし，\(b<a\) が成り立つような \(k\) 全体の集合を \(T\) とすれば，\(B_i, B_{i+1}\) の位置関係が目的通りになるための条件は次のように書くことができます．

• \(S, T\) の要素両方が列 \(X\) に現れるならば，そのうち最後の出現は \(T\) の要素である．
• さらに初期状態において \(B_{i+1}\) よりも \(B_{i}\) が右側にあるならば，\(T\) の要素が列 \(X\) に現れる

---

結局本問題は，次のような問題に言い換えることができます：

列 \(X = (k_1, \ldots, k_M)\) であって，以下の \(2\) タイプの条件 \(O(N)\) 個をすべて満たすものを数え上げよ．

[タイプ 1] \(S, T\) の要素両方が列 \(X\) に現れるならば，そのうち最後の出現は \(T\) の要素である．

[タイプ 2] 集合 \(T\) の要素は列 \(X\) に現れる．

---

[2] 答えの計算

列 \(X = (k_1, \ldots, k_M)\) に対して部分列 \(Y\) を，各 \(k\) の最後の出現だけを取り出したものとして定めます．\(X\) がタイプ 1，タイプ 2 の条件を満たすか否かは，\(Y\) が同じ条件を満たすかどうかで判定できます．よって，まず条件を満たす \(Y\) の個数を求めて，そこから \(X\) の個数を求めるという計算方法が可能です．

[2 - 1] \(Y\) に対する \(X\) の数え上げ

長さ \(n\) の列 \(Y=(y_1, \ldots, y_n)\) に対応する \(X\) の個数を求めます．

\(X\) に現れる値は，\(y_1, \ldots, y_n\) の \(n\) 種です．逆に \(y_1, \ldots, y_n\) の \(n\) 種が現れる列 \(X\) に対して，\(Y = (y_1, \ldots, y_n)\) となるものの割合は \(1/n!\) です．

したがって，\(M\) 元集合から \(n\) 元集合の全射の個数を \(\mathrm{Surj}(M, n)\) と書けば，列 \(Y\) に対応する \(X\) の個数は \(\dfrac{\mathrm{Surj}(M,n)}{n!}\) となります．

[2 - 2] \(Y\) の数え上げ

[2 - 1] より，列 \(Y\) の個数を \(|Y|\) ごとに求められれば答を計算できます．

列 \((y_1, y_2, \ldots, y_{n-1}, y_n)\) の代わりに集合の増大列 \(\emptyset \subsetneq \{y_n\} \subsetneq \{y_{n-1}, y_n\} \subsetneq \cdots\) を数えることとします．言い換えれば，列を末尾の要素から順に構築する手順を数えることにします．すると，タイプ 1 の条件は「\(T^c\) の部分集合には \(S\) の要素を追加してはいけない」と書くことができます．

タイプ 1 の条件に違反せず集合 \(s\) に至る増大列の個数 \(\mathrm{dp}[s]\) を計算することにします．この dp は，各集合 \(s\) に追加するとタイプ 1 の条件に違反してしまうような要素が列挙できていれば容易に計算できます．

各集合に追加できない要素全体は，\(T^{c}\) に \(S\) の要素を入れた後，部分集合方向に伝搬させていくことで \(O(K2^K)\) 時間で計算できます（高速ゼータ変換などと同様です）．

ここまではタイプ 2 の条件を考慮していませんが，タイプ 2 の条件を考慮するには，計算された \(\mathrm{dp}[s]\) のうち一部の \(s\) を答えに含めなければよいだけです．ここで除外すべき \(s\) も，\(O(K2^K)\) 時間で計算できます．

---

以上をまとめると，本問題は計算量 \(O(KN + K2^K + K\log M)\) 時間で解くことができます．