#P1967E1. Again Counting Arrays (Easy Version)
Again Counting Arrays (Easy Version)
Description
This is the easy version of the problem. The differences between the two versions are the constraints on and the time limit. You can make hacks only if both versions are solved.
Little R has counted many sets before, and now she decides to count arrays.
Little R thinks an array consisting of non-negative integers is continuous if and only if, for each such that , is satisfied. She likes continuity, so she only wants to generate continuous arrays.
If Little R is given and , she will try to generate a non-negative continuous array , which has no similarity with . More formally, for all , holds.
However, Little R does not have any array . Instead, she gives you , and . She wants to count the different integer arrays satisfying:
- ;
- At least one non-negative continuous array can be generated.
Note that , but the can be arbitrarily large.
Since the actual answer may be enormous, please just tell her the answer modulo .
Each test contains multiple test cases. The first line contains the number of test cases . The description of the test cases follows.
The first and only line of each test case contains three integers , , and (, , ) — the length of the array , the maximum possible element in , and the initial element of the array .
It is guaranteed that the sum of over all test cases does not exceeds .
For each test case, output a single line containing an integer: the number of different arrays satisfying the conditions, modulo .
Input
Each test contains multiple test cases. The first line contains the number of test cases . The description of the test cases follows.
The first and only line of each test case contains three integers , , and (, , ) — the length of the array , the maximum possible element in , and the initial element of the array .
It is guaranteed that the sum of over all test cases does not exceeds .
Output
For each test case, output a single line containing an integer: the number of different arrays satisfying the conditions, modulo .
Note
In the first test case, for example, when , we can set . When , we can set . In total, there are valid choices of : in fact, it can be proved that only and make it impossible to construct a non-negative continuous , so the answer is .