Шрек хоче розставити тур на шахівниці розміром 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.
Для кожного тесту виведіть єдине число — відповідь за модулем .
Приклад
У першому прикладі, всі тури вже розставлено і вони задовольняють умови:
♖ | |
♖ |
У другому прикладі, є способи розставити тури:
♖ | ||
♖ | ||
♖ |
♖ | ||
♖ | ||
♖ |
♖ | ||
♖ | ||
♖ |
♖ | ||
♖ | ||
♖ |
У третьому прикладі, є лише один спосіб:
♖ | |||
♖ | |||
♖ | |||
♖ |
У четвертому прикладі, дві тури, що розміщені знаходяться занадто далеко:
♖ | ||||
♖ |
Мангеттенська відстань між ними є 8>5, отже немає можливості розставити інші тури щоб виконувалися умови.