E. Сортируем перестановки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Пусть у вас есть перестановка a1, a2, ..., an, состоящая из чисел от 1 до n. Предположим, что за одну секунду можно выбрать набор непересекающихся пар (u1, v1), (u2, v2), ..., (uk, vk) и одновременно поменять местами aui и avi для всех i (1 ≤ ui < vi ≤ n). Пары не должны пересекаться, то есть все 2k чисел ui, vj должны быть различны.

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

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

Входные данные

В первой строке записано два целых числа n (1 ≤ n ≤ 105) и k (0 ≤ k ≤ 12). Во второй строке записана перестановка a1, ..., an (0 ≤ ai ≤ n). Если число еще не определено, вместо него записан 0. В перестановке ровно k нулей. Все числа ai, которые не равны нулю, различны.

Выходные данные

Выведите общую сумму количества способов по модулю 1000000007 (109 + 7).

Примеры
Входные данные
5 0
1 5 2 4 3
Выходные данные
6
Входные данные
5 2
1 0 2 4 0
Выходные данные
7