Shrooks#12974

Shrooks

2 seconds
512 megabytes
Very hard

Shrek wants to place rooks on a n\times n board, so that the following conditions hold:

To make things worse, Donkey already placed some rooks (fortunately, each row and each column still contains at most one rook). Find the number of ways to place the remaining rooks so that conditions hold. Since it can be large, output it modulo .

Here, the Manhattan distance between the rook in the cell on the intersection of row x_1 and column y_1 and the rook in the cell on the intersection of row x_2 and column y_2 is defined as |x_1 - x_2| + |y_1-y_2|.

Input

Each test consists of multiple test cases. The first line contains a single integer — number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer — size of the board.

The second line of each test case contains integers a_1, a_2, \ldots, a_n. If a_i = -1, it means row doesn’t yet have a rook. Otherwise, it indicates that there is a rook at the intersection of row and column a_i.

1 \leq t\leq 10^5,

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

the sum of over all test cases doesn’t exceed 2\cdot 10^5,

a_i = -1 or 1 \leq a_i \leq n for all 1\leq i \leq n,

if a_i, a_j\neq -1 for i\neq j, then a_i\neq a_j.

Output

For each test case, output a single integer, the answer modulo .

Examples

Example

Loading
Loading

Note

In the first test case, the rooks are already placed, and they satisfy the conditions:

♖

♖

In the second test case, there are ways to place rooks:

♖

♖

♖

♖

♖

♖

♖

♖

♖

♖

♖

♖

In the third test case, there is exactly one such way:

♖

♖

♖

♖

In the fourth test case, there are two rooks placed so far:

♖

♖

The manhattan distance between them is already 8>5, so there is no satisfying placement of remaining rooks.