You are an airport receptionist at Jag Airlines Group. There are 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 's baggage is 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 , 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 (in kilograms) that does not exceed the actual total weight. Here, is a given integer with .
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 .
What is probability modulo ?
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 using two coprime integers and , there is exactly one integer satisfying and . Find this .
输入格式
The input consists of multiple test cases.
The first line contains an integer (), representing the number of test cases.
test cases follow. Each test case is given in the following format.
For each test case, the first line contains integers () and (), representing the number of pieces of baggage and the parameter of the electronic scale, respectively.
The next line contains integers (), representing the weight of passenger 's baggage.
Additionally, the sum of over all test cases does not exceed .
输出格式
For the 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 (kilograms), so you cannot distinguish any of them. However, if you place two bags at a time, only the combination yields (kilograms). Therefore, the bag not placed on the scale at that moment must be the one labeled ( kilograms). Since the bags labeled and cannot be distinguished by any sequence of weighings, the maximum probability is .
:::