我们得到一个从 1 到 n 的排列序列 a1, a2, ..., an。假设在一秒钟内,我们可以选择一些不相交的对 (u1, v1), (u2, v2), ..., (uk, vk) 并同时为每个 i 交换所有 aui 和 avi (1 ≤ ui < vi ≤ n)。如果每个 ui 和 vj 彼此不同,则这些对是不相交的。
我们希望尽快按升序对序列进行完全排序。给定初始排列,计算实现此目的的方法数量。当且仅当存在时间 t 时,两种方式是不同的,使得当时用于交换的对的集合作为集合是不同的(因此对的顺序并不重要)。如果给定的排列已经排序,则排序不需要时间,因此排序的方式数为 1。
为了让问题变得更有趣,我们在排列中有 k 个洞。所以 a1, a2, ..., an 的 k 个数尚未确定。对于填充孔的每种可能性,计算方法的数量,并打印这些值的总和模 1000000007 (109 + 7)。
输入
第一行包含两个整数 n (1 ≤ n ≤ 105) 和 k (0 ≤ k ≤ 12)。第二行包含排列序列 a1, ..., an (0 ≤ ai ≤ n)。如果一个数字尚未确定,则将其表示为 0。正好有 k 个零。所有不等于零的数字 ai 都是不同的。
输出
打印路数模 1000000007 (109 + 7) 的总和。
示例
输入 #1
5 0 1 5 2 4 3
输出 #1
6
输入 #2
5 2 1 0 2 4 0
输出 #2
7