#P18223. Shrooks

Shrooks

Shrooks

Shrek 想在一个 n×nn\times n 的棋盘上放置 nn 个车,要求:

  • 每行、每列恰好有一个车;
  • 任意两个车的曼哈顿距离不超过 nn。

Donkey 已经预先放置了一些车,保证这些车中每行、每列至多一个。求将剩余车放好并满足以上要求的方案数,对 998244353998244353 取模。预先放置的车不能移动。

位于第 x1x_1 行第 y1y_1 列和第 x2x_2 行第 y2y_2 列的两个车,其曼哈顿距离定义为 ∣x1−x2∣+∣y1−y2∣|x_1-x_2|+|y_1-y_2|。

输入格式

第一行包含整数 tt,表示测试用例个数。

每个测试用例包含两行:

  • 第一行是整数 nn,表示棋盘边长;
  • 第二行有 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n。ai=−1a_i=-1 表示第 ii 行尚未放车;否则第 ii 行第 aia_i 列已经有车。

输出格式

对每个测试用例输出一行,包含一个整数,表示方案数对 998244353998244353 取模的结果。

数据范围

  • 1≤t≤1051\le t\le10^5;
  • 2≤n≤2⋅1052\le n\le2\cdot10^5;
  • 所有测试用例的 nn 之和不超过 2⋅1052\cdot10^5;
  • ai=−1a_i=-1 或 1≤ai≤n1\le a_i\le n;
  • 对不同的 i,ji,j,若 ai,aja_i,a_j 均不为 −1-1,则 ai≠aja_i\ne a_j。

样例

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

样例说明

第一例已经放完两个车,且满足条件。第二例有四种合法放法。第三例只有一种合法补全。下面保留原题中这三例的棋盘图(第二例依次画出了全部四种放法):

原题前三例的棋盘示意图

第四例的两个预置车分别在 (1,1)(1,1) 和 (5,5)(5,5),距离已经是 8>58>5,因此没有合法补全:

原题第四例的两个预置车