D1. Клуб юных авиастроителей (простая версия)
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Это easy версия задачи. Отличие между версиями заключается в том, что в этой версии все $$$a_i = 0$$$. Вы можете делать взломы только в том случае, если решили все версии этой задачи.

Есть $$$n$$$-этажный дом, этажи пронумерованы от $$$1$$$ до $$$n$$$ снизу вверх. На каждом этаже живёт ровно один человек.

У всех жителей дома сегодня есть очень важная цель: запустить всем домом суммарно хотя бы $$$c$$$ бумажных самолётиков. Жители будут запускать самолётики поочерёдно. Когда человек с $$$i$$$-го этажа запускает самолётик, это видят все жители на этажах от $$$1$$$ до $$$i$$$, пока самолёт опускается на землю.

Если с точки зрения жителя с $$$i$$$-го этажа уже было запущено хотя бы $$$c$$$ самолётиков, сам он больше не будет запускать самолётики. Также известно, что в конце дня, с точки зрения каждого из жителей дома было запущено хотя бы $$$c$$$ самолётиков, а всего было кинуто $$$m$$$ самолётиков.

Вы внимательно следили за данным флешмобом, и для каждого самолётика записывали, житель какого из этажей его кинул. Но, к сожалению, информация о том, кто именно кидал некоторые самолётики, была утеряна. Найдите количество способов заполнить пропуски, чтобы информация могла быть достоверной. Так как ответ может быть достаточно большим, выведите его по модулю $$$10^9 + 7$$$.

В этой версии задачи была утеряна вся информация, и весь массив состоит из пропусков.

Также возможна ситуация, что вы ошиблись в своих записях, и не существует ни одного возможного способа восстановить пропуски. В таком случае ответ считается равным $$$0$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит три целых числа $$$n, c, m$$$ ($$$1 \le n \le 100$$$, $$$1 \le c \le 100$$$, $$$c \le m \le n \cdot c$$$) — количество этажей в доме, минимально необходимое количество самолётиков и количество реально запущенных самолётиков.

Вторая строка каждого набора входных данных содержит $$$m$$$ целых чисел $$$a_1, a_2, \ldots, a_m$$$ ($$$0 \le a_i \le n$$$) — $$$a_i$$$ означает, житель какого этажа запускал $$$i$$$-й по счёту самолётик, $$$a_i = 0$$$ обозначает пропуск.

В этой версии задачи гарантируется, что все $$$a_i = 0$$$.

Гарантируется, что сумма значений $$$m$$$ по всем наборам входных данных не превосходит $$$10^4$$$.

Выходные данные

Для каждого набора входных данных выведите количество способов заполнить пропуски числами от $$$1$$$ до $$$n$$$, чтобы хронология запуска самолётиков могла быть достоверной, по модулю $$$10^9 + 7$$$.

Пример
Входные данные
2
3 2 4
0 0 0 0
5 5 7
0 0 0 0 0 0 0
Выходные данные
6
190
Примечание

В первом тестовом примере все шесть возможных способов заполнить пропуски таковы:

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

Обратите внимание, что массив $$$[2, 3, 1, 3]$$$ не является валидным способом заполнить пропуски, так как третий самолётик не мог быть запущен человеком с $$$1$$$ этажа, так как с его точки зрения уже было запущено $$$c = 2$$$ самолётика.

Также массив $$$[1, 1, 2, 3]$$$ не является валидным способом заполнить пропуски, так как с точки зрения человека с $$$3$$$ этажа всего был запущен только $$$1$$$ самолётик, а $$$c = 2$$$.