Sort

时间限制： 1s
空间限制： 512M

Description

对于一个 $1$ 到 $n$ 的排列 $P$，你可以进行若干次如下操作：

• 选择若干对位置，满足每个位置最多在一个位置对中，然后对每一对位置，交换这两个位置上元素的值。

设 $f(P)$ 为将 $P$ 排成升序所需的最少操作数，$g(P)$ 为以最小操作数将 $P$ 排成升序的方案数。两种方案被认为是不同的，当且仅当对于某次操作，存在一个位置 $i$，在两种方案中与 $i$ 处于同一个位置对的另一个位置不同；或者 $i$ 在一种方案中存在于一个位置对中，而在另一个方案中非然。

现在给出一个不完整的排列 $A$，其中有 $k$ 个元素未知。你需要对于 $k!$ 种可能的排列 $A$，算出这些排列 $f(A)$ 的和以及 $g(A)$ 的和。由于 $g(A)$ 的和可能很大，你只需输出对 $10^9 + 7$ 取模的结果。

Input

第一行两个整数 $n, k$。

第二行 $n$ 个整数，表示排列 $A$，其中有 $k$ 个整数为 $0$，表示这个位置上的值未知。

Output

第一行一个整数，表示所有可能的排列的 $f()$ 的和。

第二行一个整数，表示所有可能的排列的 $g()$ 的和对 $10^9 + 7$ 取模的结果。

Sample

Input

5 2
1 0 2 4 0

Output

3
7

Explanation

对于排列 $A_1 = [1, 3, 2, 4, 5]$, $f(A_1) = 1, g(A_1) = 1$；
对于排列 $A_2 = [1, 5, 2, 4, 3]$, $f(A_2) = 2, g(A_2) = 6$。

Subtasks

对所有数据，保证 $1 \leq n \leq 10^5, 0 \leq k \leq \min\{12, n\}, 0 \leq A_i \leq n$。

• Subtask1 (18%)：$k = 0, n \leq 8$；
• Subtask2–5 (45%)：$k = 0$，且存在某个非负整数 $d < n$，满足 $A_i = (i + d - 1) \mod n + 1$。其中：
  • Subtask2 (3%)：$d = 0$；
  • Subtask3 (8%)：$n, d$ 互质；
  • Subtask4 (13%)：$d = 2, n$ 为偶数；
  • Subtask5 (21%)：没有额外的约束；
• Subtask6 (11%)：$k = 0$；
• Subtask7 (17%)：$k \leq 8$；
• Subtask8 (9%)：没有特殊的约束。