F. Знакомо?
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
128 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Обратите внимание на необычное ограничение по памяти.

Рассмотрим следующий псевдокод, который обрабатывает перестановку $$$p$$$ длины $$$n$$$$$$^{\text{∗}}$$$:

function mystery(p):
    n = длина p
    st = пустой стек
    count = массив длины n из нулей 
    for i from 1 to n:
        while st не пустой и p[i] < значение на вершине стека:
            удалить элемент на вершине стека st
            count[i] = count[i] + 1
        положить p[i] в стек st
    return count

Дан массив $$$a$$$ длины $$$n$$$. Ваша задача — посчитать количество перестановок $$$p$$$ длины $$$n$$$ таких, что если $$$b$$$ — массив, возвращаемый mystery(p), то условие $$$a_i = b_i$$$ выполняется для всех $$$i$$$ ($$$1 \le i \le n$$$), где $$$a_i \neq -1$$$.

Так как ответ может быть очень большим, выведите его по модулю $$$998\,244\,353$$$.

$$$^{\text{∗}}$$$Перестановкой длины $$$n$$$ является массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ — перестановка, но $$$[1,2,2]$$$ не перестановка ($$$2$$$ встречается в массиве дважды) и $$$[1,3,4]$$$ тоже не перестановка ($$$n=3$$$, но в массиве встречается $$$4$$$).

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

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

Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$1 \le n \le 500$$$), обозначающее длину $$$a$$$.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$-1 \le a_i \le n$$$), обозначающих элементы массива $$$a$$$.

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

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

Для каждого набора входных данных выведите целое число — количество перестановок по модулю $$$998\,244\,353$$$.

Пример
Входные данные
7
1
0
1
-1
1
1
4
0 0 -1 1
6
-1 -1 -1 -1 -1 -1
3
0 1 0
7
0 -1 0 -1 2 1 -1
Выходные данные
1
1
0
3
720
2
77
Примечание

В первом и втором наборах входных данных единственная подходящая перестановка — $$$[1]$$$.

В четвёртом наборе входных данных подходящие перестановки — $$$[1,2,4,3]$$$, $$$[3,4,2,1]$$$ и $$$[1,4,3,2]$$$.

В пятом наборе входных данных подходят все перестановки длины $$$6$$$.