CF398E Sorting Permutations

给定一个长度为 $n$ 的排列序列 $a_{1},a_{2},...,a_{n}$，其中每个元素为 $1$ 到 $n$ 的某个数。假设每一秒内，你可以选择若干对不相交的下标对 $(u_{1},v_{1}),(u_{2},v_{2}),...,(u_{k},v_{k})$，并同时交换每对中的元素 $a_{u_i}$ 和 $a_{v_i}$（其中 $1 \le u_{i} < v_{i} \le n$）。若所有对中的下标都互不相同，则这些对是不相交的。 你的目标是用尽可能少的时间将该序列升序排序。对于给定的初始排列，计算能够实现这一目标的所有不同方法的数量。两种方法不同，当且仅当存在某一个时刻 $t$，其选择交换的所有下标对的集合不同（即集合不同，顺序无关）。如果初始排列已经有序，那么只需 $0$ 秒即已完成排序，此种情况下方案数为 $1$。 此外，为增加趣味性，排列中有 $k$ 个“空位”，即有 $k$ 个 $a_i$ 的值尚未确定，记作 $0$。请对于每一种填补空位的方式，分别计算完整排序的方案数，并输出所有方案数之和对 $1000000007$ 取模后的结果。

第一行包含两个整数 $n$ $(1 \le n \le 10^5)$ 和 $k$ $(0 \le k \le 12)$。 第二行包含该排列序列 $a_1, ..., a_n$，$0$ 表示空位未确定。所有非零的 $a_i$ 互不相同。

输出所有方案数的总和对 $1000000007$ $(10^9+7)$ 取模后的值。

由 ChatGPT 5 翻译