给定一个 $\{1, 2, \dots, n\}$ 的排列 $p$ 和一个非负整数 $k$。请计算 $\{1, 2, 3, 4, \dots, n\}$ 的子集 $T$，满足 $|T| = k$ 且 $|P(T) \cap T| = 0$ 的数量。

其中 $P(T)$ 表示 $P(T) = \{y \mid y = p_x, x \in T\}$。

输入格式

每个测试点包含多个测试用例。第一行包含测试用例的数量 $T$ ($1 \le T \le 15$)。

每个测试用例的描述如下：

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

第二行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$)，表示给定的排列。

$1 \le n \le 5 \times 10^5, 0 \le k \le n$。

对于所有测试用例，$\sum n \le 5 \times 10^6$。

输出格式

对于每个测试用例：

输出一行一个整数，表示答案对 $998\,244\,353$ 取模的结果。

样例

样例输入 1

3
5 1
5 3 2 1 4
5 2
2 5 1 3 4
10 3
10 9 3 8 6 4 5 7 2 1

样例输出 1

5
5
40