Club of Young Aircraft Builders (easy version)
Contest: Codeforces Round 1004 (Div. 1)
Difficulty rating: 2400
Tags: combinatorics, dp, math

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

Constraints:
Time limit: 4.0 s
Memory limit: 1024.0 MB

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

1. $$$[1, 1, 3, 3]$$$
2. $$$[1, 2, 3, 3]$$$
3. $$$[1, 3, 2, 3]$$$
4. $$$[2, 1, 3, 3]$$$
5. $$$[2, 2, 3, 3]$$$
6. $$$[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$$$.

Example input:
2
3 2 4
0 0 0 0
5 5 7
0 0 0 0 0 0 0

Example output:
6
190

Editorial:
The problem is naturally solved using dynamic programming. The author's dynamic programming approach is as follows:
Let's think: at which indices can the elements $$$a_i = 1$$$ be located? Notice that a person on the first floor can see every airplane, so the positions $$$a_{c+1} \ldots a_m$$$ cannot contain a one. However, it is entirely possible for a one to be in any subset of positions $$$\{1,2,\ldots,c\}$$$. Let's iterate $$$k$$$ from $$$0$$$ to $$$c$$$—the number of $$$a_i=1$$$ in the array. There are a total of $$$\binom{c}{k}$$$ ways to place these ones. Note that the task of placing the remaining numbers is actually analogous to the original problem with parameters $$$(n-1,c,m-k)$$$, since the launches of airplanes from the first floor do not affect the "counters" of people not on the first floor; they can simply be ignored, and we can solve the problem of placing airplanes from the remaining $$$n-1$$$ floors into the remaining $$$m-k$$$ positions.
Thus, we obtain the following dynamic programming relation: $$$dp[i][j]$$$ is the answer for $$$(n=i,m=j)$$$, with $$$c$$$ globally fixed.
Base case: $$$dp[1][c] = 1$$$
Transition: $$$dp[i][j] = \displaystyle\sum_{k=0}^c \binom{c}{k} \cdot dp[i-1][j-k]$$$
The answer is, accordingly, in $$$dp[n][m]$$$, and the overall time complexity of the solution is $$$O(n \cdot m \cdot c)$$$.
An interesting fact: the answer in the simple version of the problem can be expressed with a simple formula: $$$\binom{nc-c}{m-c}$$$. Why is this the case? No idea. If someone finds a beautiful combinatorial interpretation—please share in the comments.