Вам дана перестановка $$$a$$$ длины $$$n$$$$$$^{\text{∗}}$$$, где некоторые элементы отсутствуют и представлены как $$$-1$$$.
Определим значение перестановки как сумму MEX$$$^{\text{†}}$$$ всех её непустых подотрезков$$$^{\text{‡}}$$$.
Найдите сумму значений всех возможных допустимых перестановок, которые могут быть сформированы путем заполнения отсутствующих элементов в $$$a$$$ по модулю $$$10^9 + 7$$$.
$$$^{\text{∗}}$$$ Перестановка длины $$$n$$$ — это массив, состоящий из $$$n$$$ различных целых чисел от $$$\bf{0}$$$ до $$$\bf{n - 1}$$$ в произвольном порядке. Например, $$$[1,2,0,4,3]$$$ является перестановкой, но $$$[0,1,1]$$$ не является перестановкой (число $$$1$$$ встречается дважды в массиве), и $$$[0,2,3]$$$ также не является перестановкой (при $$$n=3$$$ в массиве есть $$$3$$$).
$$$^{\text{†}}$$$Наименьшее исключенное (MEX) набора чисел $$$c_1, c_2, \ldots, c_k$$$ определяется как наименьшее неотрицательное целое число $$$x$$$, которое не встречается в наборе чисел $$$c$$$.
$$$^{\text{‡}}$$$Последовательность $$$a$$$ является подотрезком последовательности $$$b$$$, если $$$a$$$ может быть получена из $$$b$$$ удалением нескольких (возможно, ни одного или всех) элементов с начала и нескольких (возможно, ни одного или всех) элементов с конца.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 5000$$$).
Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$-1 \le a_i \lt n$$$).
Гарантируется, что элементы $$$a$$$, которые не равны $$$-1$$$, различны.
Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$5000$$$.
Для каждого набора входных данных выведите одно целое число — сумму значений всех возможных допустимых перестановок по модулю $$$10^9 + 7$$$.
520 -12-1 -132 0 13-1 2 -15-1 0 -1 2 -1
3 6 7 10 104
В первом наборе входных данных единственной допустимой перестановкой является $$$[0, 1]$$$, и значение $$$[0, 1]$$$ равно $$$3$$$, так как:
$$$$$$\operatorname{mex}([0]) + \operatorname{mex}([1]) + \operatorname{mex}([0, 1]) = 1 + 0 + 2 = 3$$$$$$
Таким образом, ответ равен $$$3$$$.
Во втором наборе входных данных есть две допустимые перестановки: $$$[0, 1]$$$ и $$$[1, 0]$$$. Значение $$$[0, 1]$$$ и значение $$$[1, 0]$$$ равны $$$3$$$, поэтому ответ равен $$$3 + 3 = 6$$$.
В четвертом наборе входных данных есть две допустимые перестановки: $$$[0, 2, 1]$$$ и $$$[1, 2, 0]$$$. Значение $$$[0, 2, 1]$$$ равно $$$5$$$, так как:
$$$$$$\operatorname{mex}([0]) + \operatorname{mex}([2]) + \operatorname{mex}([1]) + \operatorname{mex}([0, 2]) + \operatorname{mex}([2, 1]) + \operatorname{mex}([0, 2, 1]) = 1 + 0 + 0 + 1 + 0 + 3 = 5$$$$$$
А значение $$$[1, 2, 0]$$$ равно $$$5$$$, так как:
$$$$$$\operatorname{mex}([1]) + \operatorname{mex}([2]) + \operatorname{mex}([0]) + \operatorname{mex}([1, 2]) + \operatorname{mex}([2, 0]) + \operatorname{mex}([1, 2, 0]) = 0 + 0 + 1 + 0 + 1 + 3 = 5$$$$$$
Таким образом, ответ равен $$$5 + 5 = 10$$$.
