B. Beautiful Trees
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

As everyone knows, the Legendary Huron loves playing with magnetic sticks of many colors. After finishing his colorful polygon constructions last Saturday, he now wants to store his sticks in boxes.

Legendary Huron owns $$$m$$$ magnetic sticks. Each stick has a color, represented by an integer in the range $$$[0, m-1]$$$. Sticks of the same color are indistinguishable.

He plans to store these sticks in $$$n$$$ distinct boxes. Each stick must be placed in exactly one box.

Once the sticks are distributed, Legendary Huron will hang the boxes in the form of a colorful rooted tree:

  • One box will be chosen as the root and hung directly from the ceiling.
  • Every other box will be hung directly from exactly one parent box, forming a tree structure with $$$n$$$ nodes (the boxes).

Legendary Huron defines the beauty of his arrangement as follows:

  • Beauty of a box: the MEX of the colors inside that box. Recall that the MEX of a multiset of integers is the smallest non-negative integer that does not belong to the multiset. For example, if a box contains sticks of colors $$$\{0,2,2,5\}$$$, its beauty is $$$1$$$.
  • Beauty of a path: the product of the beauties of all boxes along that path.
  • Beauty of the tree: the sum of the beauties of all $$$n^2$$$ simple paths in the tree (including single-box paths).

Legendary Huron is still undecided about two things:

  1. How to distribute the $$$m$$$ sticks among the $$$n$$$ boxes.
  2. How to hang the boxes as a rooted tree.

He wants to know the total sum of beauties of the trees over all possible valid configurations. Two configurations are considered different if:

  • The tree structures differ (different root or different set of edges), or
  • There exists at least one box whose multiset of colors differs.

Note: The boxes are distinct (labeled), but the sticks of the same color are indistinguishable.

Input

The file contains multiple test cases. The first line contains an integer $$$t$$$ $$$(1 \leq t \leq 10^5)$$$ — the number of test cases.

The first line of each test case description contains two integers $$$n$$$ and $$$m$$$ $$$(1 \leq n, m \leq 10^6)$$$.

The following line contains $$$m$$$ integers between $$$0$$$ and $$$m-1$$$, representing the colors of each magnetic stick.

It is guaranteed that the sum of all values of $$$m$$$ over the input does not exceed $$$10^6$$$.

Output

For each test case, answer modulo $$$998244353$$$ — the total sum of beauties of the trees over all possible ways of distributing the sticks and constructing the colorful rooted tree.

Examples
Input
3
1 3
0 1 2
2 3
0 1 2
3 3
0 1 2
Output
3
28
351
Input
1
10 7
3 0 1 2 0 3 1
Output
335613770