Sorting Permutations

We are given a permutation sequence a₁, a₂, ..., a_n of numbers from 1 to n. Let's assume that in one second, we can choose some disjoint pairs (u₁, v₁), (u₂, v₂), ..., (u_k, v_k) and swap all a_ui and a_vi 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₁, a₂, ..., 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 (10⁹ + 7).