Пусть у вас есть перестановка a₁, a₂, ..., a_n, состоящая из чисел от 1 до n. Предположим, что за одну секунду можно выбрать набор непересекающихся пар (u₁, v₁), (u₂, v₂), ..., (u_k, v_k) и одновременно поменять местами a_ui и a_vi для всех i (1 ≤ u_i < v_i ≤ n). Пары не должны пересекаться, то есть все 2k чисел u_i, v_j должны быть различны.

Вы хотите отсортировать заданную перестановку по возрастанию как можно быстрее с помощью описанных операций. Вычислите количество способов, которыми это можно сделать. Два способа различны тогда и только тогда, когда существует такой момент времени t, что в этих способах в этот момент времени выбраны два различных множества пар (порядок пар не имеет значения). Если заданная перестановка уже отсортирована, на ее сортировку не требуется времени. Таким образом, количество способов сортировки равно 1.

Для того, чтобы усложнить задачу, мы выкинули k чисел из перестановки. Теперь ровно k чисел перестановки a₁, a₂, ..., a_n еще не определены. Для каждого возможного способа расставить выкинутые числа в перестановке a, нужно посчитать описанное количество способов сортировки и вывести сумму этих значений по модулю 1000000007 (10⁹ + 7).