Hints → https://atcoder.jp/contests/arc158/editorial/5987

---

[1] Transform the condition

Let us represent a way to execute the process as the sequence of chosen \(k\): \(X = (k_1, \ldots, k_M)\). When does \(X\) satisfy the condition?

Stable sort does not reorder elements with the same values, so it can be uniquely determined which \(A_i\) each \(B_i\) derives from. \(B_1, B_2, \ldots, B_N\) will be arranged in the desired order if and only if for every \(i\), \(B_{i+1}\) is to the right of \(B_i\).

Below, the “positional relationship” between \(B_i\) and \(B_{i+1}\) means which of these two is to the left.

Let us fix \(i\) and focus only on the positional relationship of \(B_i\) and \(B_{i+1}\). Each stable sort changes this positional relationship, where \(a\) and \(b\) are the \(k\)-th lowest digits of \(B_i\) and \(B_{i+1}\), respectively.

• If \(a<b\), then \(B_{i+1}\) will be to the right of \(B_i\).
• If \(a=b\), then the positional relationship of \(B_i\) and \(B_{i+1}\) does not change.
• If \(a>b\), then \(B_i\) will be to the right of \(B_{i+1}\).

Thus, if \(S\) is the set of all \(k\) such that \(a<b\), and \(T\) is the set of all \(k\) such that \(b<a\), we will have the desired positional relationship of \(B_i\) and \(B_{i+1}\) when the following conditions are satisfied.

• If there are elements of \(S\) and those of \(T\) in the sequence \(X\), then the last of those occurrences is that of an element of \(T\).
• Additionally, if \(B_{i}\) is to the right of \(B_{i+1}\) in the initial state, then there is an element of \(T\) in \(X\).

---

Eventually, the problem can be transformed into the following one:

Count sequences \(X = (k_1, \ldots, k_M)\) that satisfy all \(O(N)\) conditions of the following two types.

[Type 1] If there are elements of \(S\) and those of \(T\) in the sequence \(X\), then the last of those occurrences is that of an element of \(T\).

[Type 2] There is an element of \(T\) in \(X\).

---

[2] Compute the answer

For a sequence \(X = (k_1, \ldots, k_M)\), let us define its subsequence \(Y\) that contains the last occurrence of each \(k\). We can check whether \(X\) satisfies conditions of types 1 and 2 by checking whether \(Y\) satisfies the same conditions. Thus, we can first find the number of \(Y\) that satisfy the condition, and then find the number of corresponding \(X\).

[2 - 1] Count \(X\) corresponding to \(Y\)

Let us count \(X\) corresponding to a length-\(n\) sequence \(Y=(y_1, \ldots, y_n)\).

\(X\) contains \(n\) kinds of values: \(y_1, \ldots, y_n\). On the other hand, for the sequences \(X\) containing the \(n\) kinds of values \(y_1, \ldots, y_n\), exactly \(1/n!\) of them makes \(Y = (y_1, \ldots, y_n)\).

Thus, the number of \(X\) corresponding to a sequence \(Y\) is \(\dfrac{\mathrm{Surj}(M,n)}{n!}\), where \(\mathrm{Surj}(M, n)\) is the number of surjections from an \(M\)-element set to an \(n\)-element set.

[2 - 2] Count \(Y\)

From [2 - 1], we can compute the answer if we can find the number of sequences \(Y\) for each \(|Y|\).

Instead of sequences \((y_1, y_2, \ldots, y_{n-1}, y_n)\), let us count increasing sequences of sets \(\emptyset \subsetneq \{y_n\} \subsetneq \{y_{n-1}, y_n\} \subsetneq \cdots\). In other words, let us count the number of ways to construct the sequences from back to front. Then, a type-\(1\) condition can be written as: “no element of \(S\) should be added to any subset of \(T^c\).”

Let us compute \(\mathrm{dp}[s]\): the number of increasing sequences leading to the set \(s\) without violating type-\(1\) conditions. We can compute this dp easily if, for each set \(s\), the elements whose addition would violate type-\(1\) conditions are already enumerated.

The elements that cannot be added to each set can be computed by first inserting the elements of \(S\) into \(T^{c}\) and then propagating them toward their subsets in \(O(K2^K)\) time (similarly to fast zeta transform and such).

So far, we have not considered type-\(2\) conditions, but to do so, we only have to exclude some \(s\) from the computed \(\mathrm{dp}[s]\). The \(s\) to exclude can also be computed in \(O(K2^K)\) time.

---

From all of the above, the problem can be solved in a time complexity of \(O(KN + K2^K + K\log M)\).