祖先关系

时间限制：2s
空间限制：512MB

题目描述

给定一个元素均为 $0$ 或 $1$ 的 $N\times N$ 矩阵 $A=(A_{i,j})$。求满足下列条件的、顶点编号为 $1$ 到 $N$ 的树 $G$ 的数量，对 $998244353$ 取模。

将 $G$ 以顶点 $1$ 为根。对于任意 $i,j$，$A_{i,j}=1$ 当且仅当 $i$ 是 $j$ 的祖先或 $j$ 是 $i$ 的祖先。顶点自身也视为自己的祖先。

有 $T$ 组测试数据。

输入格式

第一行输入整数 $T$。每组数据先输入整数 $N$，随后输入 $N$ 行，每行 $N$ 个整数，表示矩阵 $A$。

输出格式

对每组数据输出一行答案，对 $998244353$ 取模。

样例输入 1

5
3
1 1 1
1 1 0
1 0 1
3
1 1 1
1 1 1
1 1 1
3
1 0 0
0 1 0
0 0 1
3
1 0 1
0 1 1
1 1 1
7
1 1 1 1 1 1 1
1 1 0 1 0 1 1
1 0 1 1 1 1 0
1 1 1 1 1 1 1
1 0 1 1 1 1 0
1 1 1 1 1 1 1
1 1 0 1 0 1 1

样例输出 1

1
2
0
0
8

数据范围

• $1\le T\le 10^5$
• $2\le N\le 400$
• $A_{i,j}\in\{0,1\}$
• $A_{i,i}=1$
• $A_{i,j}=A_{j,i}$
• 所有测试数据的 $N^2$ 之和不超过 $400^2$

附件数据

• 子任务 1：输入　输出
• 子任务 2：输入　输出
• 子任务 3：输入　输出
• 子任务 4：输入　输出