给定一个排列 $p_1, p_2, \dots, p_n$。你可以重复执行以下操作：

• 选择一个区间 $p_l, p_{l+1}, \dots, p_{l+c}$ ($1 \le l, l+c \le n$)，其中 $p_l$ 是该区间内的最小值，你可以任意排列 $p_{l+1}, \dots, p_{l+c}$。
• 选择一个区间 $p_l, p_{l+1}, \dots, p_{l+c}$ ($1 \le l, l+c \le n$)，其中 $p_{l+c}$ 是该区间内的最小值，你可以任意排列 $p_l, \dots, p_{l+c-1}$。

你想知道通过这些操作可以得到多少种不同的排列。答案可能很大，请输出答案对 $998244353$ 取模的结果。

输入格式

第一行包含一个整数 $T$，表示测试用例的数量 ($1 \le T \le 100000$)。

每个测试用例的第一行包含两个整数 $n$ 和 $c$ ($2 \le c \le 500000, 2 \le n \le 500000$)。所有测试用例的 $n$ 之和不超过 $500000$。

每个测试用例的第二行包含一个排列 $p_1, \dots, p_n$ ($1 \le p_i \le n$)。

输出格式

对于每个测试用例，输出一行，包含答案对 $998244353$ 取模的结果。

样例

输入格式 1

5
5 3
3 4 2 1 5
5 4
4 2 1 3 5
5 2
4 5 3 1 2
5 3
4 3 2 1 5
5 2
2 3 1 5 4

输出格式 1

6
1
4
6
4