P15789 [JAG 2025 Summer Camp #3] Broken Scale

You are an airport receptionist at Jag Airlines Group. There are $N$ passengers, and you have received one piece of baggage from each of them. From the check-in records, you know that the weight of passenger $i$'s baggage is $A_i$ kilograms. However, you forgot to attach labels to the bags. If you assign random labels to the bags, the probability of attaching the correct label to all baggage is $\frac{1}{N!}$, which is far too low. While thinking of ways to increase this probability, you find a slightly broken electronic scale in the warehouse. After some investigation, you find that when items are placed on this scale, it displays the largest value among $B^0, B^1, B^2, \ldots$ (in kilograms) that does not exceed the actual total weight. Here, $B$ is a given integer with $B \geq 2$. You may place any non-empty subset of the bags on the scale, and you may repeat this as many times as you like. Find the maximum probability of attaching the correct label to all baggage if you act optimally, and output it modulo $998244353 = 119 \times 2^{23} + 1$. ### What is probability modulo $998244353$? It can be proved that the sought probabilities will always be rational numbers. Under the constraints of this problem, it can also be proved that when expressing the value as $\frac{P}{Q}$ using two coprime integers $P$ and $Q$, there is exactly one integer $R$ satisfying $R \times Q \equiv P \pmod{998244353}$ and $0 \leq R < 998244353$. Find this $R$.

The input consists of multiple test cases. The first line contains an integer $T$ ($1 \leq T \leq 10$), representing the number of test cases. $T$ test cases follow. Each test case is given in the following format. $$\begin{aligned} & N \ B \\ & A_1 \ A_2 \ \ldots \ A_N \end{aligned}$$ For each test case, the first line contains integers $N$ ($1 \leq N \leq 300$) and $B$ ($2 \leq B \leq 1500$), representing the number of pieces of baggage and the parameter of the electronic scale, respectively. The next line contains $N$ integers $A_i$ ($1 \leq A_1 \leq A_2 \leq \cdots \leq A_N \leq 1500$), representing the weight of passenger $i$'s baggage. Additionally, the sum of $N$ over all test cases does not exceed $300$.

For the $T$ test cases, output the answers separated by newlines. For each test case, output the maximum probability of attaching the correct label to all baggage if you act optimally.

In the first test case, if you place one bag at a time, the scale always shows $3^2 = 9$ (kilograms), so you cannot distinguish any of them. However, if you place two bags at a time, only the combination $15 + 17$ yields $3^3 = 27$ (kilograms). Therefore, the bag not placed on the scale at that moment must be the one labeled $1$ ($9$ kilograms). Since the bags labeled $2$ and $3$ cannot be distinguished by any sequence of weighings, the maximum probability is $\frac{1}{2}$. :::align{center}  :::