This is the hard version of the problem. The difference between the versions is that in this version, not necessary (a_i = 0). You can hack only if you solved all versions of this problem. There is a building with (n) floors, numbered from (1) to (n) from bottom to top. There is exactly one person living on each floor. All the residents of the building have an important goal today: to launch at least (c) paper airplanes collectively. The residents will launch the airplanes in turn. When a person from the (i)-th floor launches an airplane, all residents on floors from (1) to (i) can see it as it descends to the ground. If, from the perspective of the resident on the (i)-th floor, at least (c) airplanes have already been launched, they will no longer launch airplanes themselves. It is also known that by the end of the day, from the perspective of each resident in the building, at least (c) airplanes have been launched, and a total of (m) airplanes were thrown. You have been carefully monitoring this flash mob, and for each airplane, you recorded which resident from which floor threw it. Unfortunately, the information about who exactly threw some of the airplanes has been lost. Find the number of ways to fill in the gaps so that the information could be credible. Since the answer could be quite large, output it modulo (10^9 + 7). It is also possible that you made a mistake in your records, and there is no possible way to restore the gaps. In that case, the answer is considered to be (0). Each test contains multiple test cases. The first line contains the number of test cases (t) ((1 \le t \le 10^4)). The description of the test cases follows. The first line of each test case contains three integers (n, c, m) ((1 \le n \le 100), (1 \le c \le 100), (c \le m \le n \cdot c)) — the number of floors in the building, the minimum required number of airplanes, and the number of airplanes a