23460번 - Permutation 다국어

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$.

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$).

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