QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 1024 MB Total points: 100 Hackable ✓
Statistics

时间限制2s,空间限制1GB

给出一个$n\times n$的$01$矩阵$c$,求有多少长度为$n$的$01$序列$a,b$,满足$c_{i,j}=a_i$或$c_{i,j}=b_j$,答案对$998244353$取模。

输入格式

第一行一个整数$n$表示矩阵大小。

接下来$n$行,每行一个长度为$n$的$01$字符串$c_i$,其中第$j$个字符表示$c_{i,j}$。

输出格式

一行一个整数表示答案对$998244353$取模后的结果。

样例输入

input

3
010
101
010

样例输出

input

2

限制与约定

$subtask1(5\%):n\leq 10$

$subtask2(15\%):n\leq 20$

$subtask3(40\%):n\leq 300$

$subtask4(5\%):c矩阵随机$

$subtask5(35\%):没有特殊限制$

$1\leq n \leq 5000,0\leq c_{i,j}\leq 1$