E. Play It by Ear
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are playing a popular card game. There are $$$2n$$$ distinct cards labeled $$$1$$$ through $$$2n$$$, shuffled uniformly at random and piled up into a deck. You draw the top $$$n$$$ cards as your starting hand, and the remaining deck order is hidden from you. Each turn, you choose any one card from your hand, play it by placing it at the bottom of the deck, and then draw the current top card, so your hand size remains $$$n$$$.

You have $$$m$$$ quests to complete in order: the $$$i$$$-th quest requires you to play the card labeled $$$a_i$$$, and it becomes active only after the $$$(i-1)$$$-th quest is completed (unless it is the first quest, which is initially active). Playing the card labeled $$$a_i$$$ before the $$$i$$$-th quest is active does not count toward the $$$i$$$-th quest. You know any of $$$a_1, a_2, \ldots, a_m$$$ (values may repeat) in advance.

Assuming you play cards under the optimal pure strategy, compute the minimum expected number of turns needed to complete all $$$m$$$ quests over the random initial shuffle, modulo $$$998\,244\,353$$$.

Formally, a pure strategy means that at each turn, the card chosen depends only on the observable history, and identical known information (initial hand, respective played and drawn cards in past turns, and quest completion status) deterministically yields the same chosen card. For a pure strategy $$$\sigma$$$ and an initial shuffle $$$\pi$$$, let $$$f_\sigma(\pi)$$$ be the number of turns needed to complete all $$$m$$$ quests when following $$$\sigma$$$; the value to be computed equals $$$\left(\min_{\sigma} E\!\left[f_\sigma(\pi)\right]\right) \bmod 998\,244\,353$$$, where the expectation $$$E[\cdot]$$$ is taken over the uniform distribution on all $$$(2n)!$$$ possible shuffles of the initial deck.

Input

The first line of the input contains an integer $$$T$$$ ($$$1 \le T \le 1\,000$$$), denoting the number of test cases. For each test case:

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 5\,000$$$, $$$1 \le m \le 2 \times 10^5$$$).

The second line contains $$$m$$$ integers $$$a_1, a_2, \ldots, a_m$$$ ($$$1 \le a_i \le 2n$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5\,000$$$, and the sum of $$$m$$$ over all test cases does not exceed $$$2 \times 10^5$$$.

Output

For each test case, since the minimum expected number of turns can be denoted by an irreducible fraction $$$\frac{p}{q}$$$, you only need to print an integer $$$r$$$ in one line satisfying $$$0 \le r \lt 998\,244\,353$$$ and $$$r \cdot q \equiv p \pmod{998\,244\,353}$$$. It can be proved that such $$$r$$$ exists and is unique.

Example
Input
3
2 1
1
3 7
2 5 1 2 6 2 1
1000 2
1116 1116
Output
249561090
299473317
748684517
Note

For the first test case of the sample case, an optimal pure strategy is: if the card labeled $$$1$$$ is in your initial hand, play it immediately; otherwise repeatedly play any card until you draw it and play it in your next turn. Hence the minimum expected number of turns is $$$\frac12 \times 1+\frac14 \times 2+\frac14 \times 3=\frac{7}{4}$$$.