Problem Statement

You are given integers $N,K$ and an integer sequence $A=(A_1,A_2,\ldots,A_K)$ of length $K$. It is guaranteed that each element of $A$ is between $1$ and $N$, inclusive, and all elements are distinct.

For a permutation $P=(P_1,P_2,\ldots,P_N)$ of $(1,2,\ldots,N)$, define $f(P)$ as follows.

• The maximum number of times the following operation can be performed on $P$.
• Choose $2\le i\le N$ satisfying $P_i < \max(P_1,P_2,\ldots,P_{i-1})$, and move $P_i$ to the front. That is, replace $P$ with $(P_i,P_1,P_2,\ldots,P_{i-1},P_{i+1},\ldots,P_N)$.

There are $(N-K)!$ permutations $P$ of $(1,2,\ldots,N)$ satisfying $P_i=A_i$ for $i=1,2,\ldots,K$. Find the sum, modulo $998244353$, of $f(P)$ over all such permutations.

You are given $T$ test cases; solve each of them.

Constraints

• $1\le T\le 10^5$
• $1\le K\le N$
• The sum of $N$ over all test cases is at most $5\times 10^5$.
• $1\le A_i\le N$
• All elements of $A$ are distinct.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

Each test case is given in the following format:

N K
A_1 A_2 \ldots A_K

Output

Output the answer for the test cases in order, separated by newlines.