給定一個排列 $p_1, p_2, \dots, p_n$。你可以重複進行以下操作：

• 選擇一個區間 $p_l, p_{l+1}, \dots, p_{l+c}$ ($l \ge 1, l+c \le n$)，其中 $p_l$ 是該區間中的最小值，你可以任意排列 $p_{l+1}, \dots, p_{l+c}$。
• 選擇一個區間 $p_l, p_{l+1}, \dots, p_{l+c}$ ($l \ge 1, 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