CF398E.Sorting Permutations

We are given a permutation sequence _a_1, _a_2, ..., a__n of numbers from 1 to n. Let's assume that in one second, we can choose some disjoint pairs (_u_1, _v_1), (_u_2, _v_2), ..., (u__k, v__k) and swap all a__u__i and a__v__i for every i at the same time (1 ≤ u__i < v__i ≤ n). The pairs are disjoint if every u__i and v__j are different from each other.

We want to sort the sequence completely in increasing order as fast as possible. Given the initial permutation, calculate the number of ways to achieve this. Two ways are different if and only if there is a time t, such that the set of pairs used for swapping at that time are different as sets (so ordering of pairs doesn't matter). If the given permutation is already sorted, it takes no time to sort, so the number of ways to sort it is 1.

To make the problem more interesting, we have k holes inside the permutation. So exactly k numbers of _a_1, _a_2, ..., a__n are not yet determined. For every possibility of filling the holes, calculate the number of ways, and print the total sum of these values modulo 1000000007 (109 + 7).

我们给定一个由 $1$ 到 $n$ 构成的排列序列 $a_1,\,a_2,\,\dots,\,a_n$。假设在 1 秒内，我们可以选择若干互不相交的数对 $(u_1,\,v_1),\,(u_2,\,v_2),\,\dots,\,(u_k,\,v_k)$，并同时交换所有 $a_{u_i}$ 与 $a_{v_i}$（对每个 $i$）（其中 $1 \le u_i < v_i \le n$）。这些数对称为“互不相交”的，当且仅当所有 $u_i$ 和 $v_j$ 彼此互不相同。

我们的目标是以最短时间将该序列完全按升序排序。给定初始排列，计算达成该目标的方案总数。两种方案被视为不同，当且仅当存在某个时刻 $t$，使得该时刻所使用的交换数对集合不同（即只考虑集合，不考虑数对的顺序）。若给定排列已排好序，则无需任何操作，此时方案数为 $1$。

为了使问题更有趣，该排列中存在 $k$ 个“空位”（holes）。即在 $a_1,\,a_2,\,\dots,\,a_n$ 中，恰好有 $k$ 个位置的数值尚未确定。对每一种填满这些空位的可能方式（即每种合法的填充方案），计算其对应的排序方案数；最后输出所有这些方案数之和对 $1000000007$（即 $10^9 + 7$）取模的结果。

The first line contains two integers n (1 ≤ n ≤ 105) and k (0 ≤ k ≤ 12). The second line contains the permutation sequence _a_1, ..., a__n (0 ≤ a__i ≤ n). If a number is not yet determined, it is denoted as 0. There are exactly k zeroes. All the numbers a__i that aren't equal to zero are distinct.

第一行包含两个整数 $n$（$1 \leq n \leq 10^5$）和 $k$（$0 \leq k \leq 12$）。第二行包含一个排列序列 $a_1, \dots, a_n$（$0 \leq a_i \leq n$）。若某个数尚未确定，则用 $0$ 表示。序列中恰好有 $k$ 个零。所有不等于零的 $a_i$ 互不相同。

Print the total sum of the number of ways modulo 1000000007 (109 + 7).

输出方案总数对 1000000007（$10^9 + 7$）取模的结果。