Тури#12974

Тури

2 секунди
512 мегабайтів
Дуже складна

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

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

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

Вхідні дані

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

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

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

1 \leq t\leq 10^5,

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

Сума по всіх тестах не перевищує 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.

Вихідні дані

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

Приклади

Приклад

Loading
Loading

Примітка

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

♖

♖

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

♖

♖

♖

♖

♖

♖

♖

♖

♖

♖

♖

♖

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

♖

♖

♖

♖

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

♖

♖

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