Background

Time takes the camera away, without thinking. Memories will not let go.

Problem Description

You have an array $a$ of length $n$. Xiao Q wants you to split it into at most $m$ non-empty consecutive segments, and the numbers in each segment must be strictly increasing. Now Xiao Q wants to know how many splitting plans there are in total. Since the number of plans may be very large, you only need to output the result modulo $998244353$.

Input Format

This problem contains multiple test cases.

The first line contains an integer $T$, which indicates the number of test cases.

Then follow $T$ test cases. Each test case is given in the following format:

The first line contains two integers $n,m$, representing the array length and the segment limit.

The second line contains $n$ integers $a_1,a_2\dots a_n$.

Output Format

For each test case, output one line containing one integer, which is the number of plans modulo $998244353$.

2
3 2
2 3 1
10 5
7 10 9 23 1 6 7 8 9 20

1
29

Hint

Sample Explanation

• For the first test case, there is only one plan: $[2,3],[1]$.

Constraints

This problem uses bundled testdata.

• Subtask 0 (0 pts): samples.
• Subtask 1 (10 pts): $\sum n\le 10$.
• Subtask 2 (20 pts): $\sum n\le 1000$.
• Subtask 3 (10 pts): the array itself is guaranteed to be strictly increasing.
• Subtask 4 (30 pts): $\sum n\le 10^6$.
• Subtask 5 (30 pts): $\sum n\le 10^7$.

For all testdata, it is guaranteed that $1\le \sum n\le 10^7,1\le m\le n,1\le a_i\le 10^9$.

Translated by ChatGPT 5