Дана перестановка $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