Тури

Обмеження: 2 сек., 512 МіБ

Шрек хоче розставити \(n\) тур на шахівниці розміром \(n\times n\), так щоб виконувалися наступні умови:

• В кожному рядку та стовпці є рівно \(1\) тура;

• Мангеттенська відстань між будь-якою парою тур не перевищує \(n\).

Щоб Шреку не було так просто, Віслюк вже розставив декілька тур на дошку (на щастя кожен рядок та стовпець мають не більше однієї тури). Знайдять кількість способів розставити всі інші тури, щоб виконувилися всі умови. Оскільки відповідь може бути великою виведіть її за модулем \(998244353\).

Тут мангеттенська відстань між турою в клітинці на перетині рядка \(x_1\) та стовпця \(y_1\) і турою в клітинці на перетині рядка \(x_2\) та стовпця \(y_2\) визначається як \(|x_1 - x_2| + |y_1 - y_2|\).

Вхідні дані

Вам потрібно опрацювати декілька тестів. В першому рядку задано одне ціде число \(t\) — кількість тестів. Після цього буде задано опис кожного тесту.

В першому рядку кожного тесту задано одне ціле число \(n\) — розмір шахівниці.

В другому рядку кожного тесту задано \(n\) цілих чисел \(a_1, a_2, \ldots, a_n\). Якщо \(a_i = -1\), то в рядку \(i\) немає тури. В іншому випадку число \(a_i\) вказує, що тура розміщена на перетині \(i\)-того рядка та \(a_i\)-того стовпця.

Вихідні дані

Для кожного тесту виведіть єдине число — відповідь за модулем \(998244353\).

Обмеження

\(1 \leq t\leq 10^5\),

\(2 \leq n\leq 2\cdot 10^5\),

Сума \(n\) по всіх тестах не перевищує \(2\cdot 10^5\),

\(a_i = -1\) або \(1 \leq a_i \leq n\) для всіх \(1\leq i \leq n\),

якщо \(a_i, a_j\neq -1\) для \(i\neq j\), тоді \(a_i\neq a_j\).

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
6 2 1 2 3 -1 -1 -1 4 1 -1 -1 -1 5 1 -1 -1 -1 5 6 3 -1 -1 -1 -1 4 10 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1	1 4 1 0 6 92

Примітки

У першому прикладі, всі тури вже розставлено і вони задовольняють умови:

♖
	♖

 

У другому прикладі, є \(4\) способи розставити тури:

♖
		♖
	♖

   

		♖
♖
	♖

   

	♖
♖
		♖

   

	♖
		♖
♖

 

У третьому прикладі, є лише один спосіб:

♖
			♖
		♖
	♖

 

У четвертому прикладі, дві тури, що розміщені знаходяться занадто далеко:

♖
				♖

Мангеттенська відстань між ними є \(8>5\), отже немає можливості розставити інші тури щоб виконувалися умови.