This is the easy version of the problem. The difference between the versions is that in this version, all $$$a_i = 0$$$. You can hack only if you solved all versions of this problem.

There is an $$$n$$$-story building, with 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 a very 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 the 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 not launch any more 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 carefully monitored this flash mob and recorded which resident from which floor threw each airplane. Unfortunately, the information about who exactly threw some airplanes has been lost. Find the number of ways to fill in the gaps so that the information could be credible. Since the answer can be quite large, output it modulo $$$10^9 + 7$$$.

In this version of the problem, all information has been lost, and the entire array consists of gaps.

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$$$.

Input

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 actually launched.

The second line of each test case contains $$$m$$$ integers $$$a_1, a_2, \ldots, a_m$$$ ($$$0 \le a_i \le n$$$) — $$$a_i$$$ indicates the resident from which floor launched the $$$i$$$-th airplane; $$$a_i = 0$$$ indicates a gap.

In this version of the problem, it is guaranteed that all $$$a_i = 0$$$.

It is guaranteed that the sum of the values of $$$m$$$ across all test cases does not exceed $$$10^4$$$.

Output

For each test case, output the number of ways to fill in the gaps with numbers from $$$1$$$ to $$$n$$$, so that the chronology of the airplane launches could be credible, modulo $$$10^9 + 7$$$.

Note

In the first test example, all six possible ways to fill in the gaps are as follows:

$$$[1, 1, 3, 3]$$$
$$$[1, 2, 3, 3]$$$
$$$[1, 3, 2, 3]$$$
$$$[2, 1, 3, 3]$$$
$$$[2, 2, 3, 3]$$$
$$$[3, 1, 2, 3]$$$

Note that the array $$$[2, 3, 1, 3]$$$ is not a valid way to fill in the gaps, as the third airplane could not have been launched by the person on the $$$1$$$st floor, since from their perspective, $$$c = 2$$$ airplanes had already been launched.

Also, the array $$$[1, 1, 2, 3]$$$ is not a valid way to fill in the gaps, as from the perspective of the person on the $$$3$$$rd floor, only $$$1$$$ airplane has been launched, while $$$c = 2$$$.

Club of Young Aircraft Builders (easy version)

Examples