J. Permutation
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a permutation $$$p_1, p_2, \dots, p_n$$$. You can do the following operations repeatedly:

  • Choose an interval $$$p_{l}, p_{l+1}, \dots, p_{l+c} (l \geq 1, l+c \leq n)$$$ where $$$p_l$$$ is the smallest element in this interval, you can permutate $$$p_{l+1}, \dots, p_{l+c}$$$ in arbitrary way.
  • Choose an interval $$$p_{l}, p_{l+1}, \dots, p_{l+c} (l\geq 1, l+c \leq n)$$$ where $$$p_{l+c}$$$ is the smallest element in this interval, you can permutate $$$p_{l}, \dots, p_{l+c-1}$$$ in arbitrary way.

You want to know how many distinct permutations you can get using operations. The answer can be large, output the answer modulo $$$998244353$$$.

Input

The first line contains an integer $$$T$$$ denoting the number of test cases ($$$1\le T\le 100000$$$).

The first line in a test case contains two integers $$$n$$$ and $$$c$$$ ($$$2\le c \le 500000$$$, $$$2\le n\le 500000$$$). The sum of $$$n$$$ over all test cases does not exceed $$$500000$$$.

The second line in a test case contains a permutation $$$p_1,\ldots, p_n$$$ ($$$1\le p_i\le n$$$).

Output

For each test case, output one line containing the answer modulo $$$998244353$$$.

Example
Input
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
Output
6
1
4
6
4