[AdditionalFile3627.zip](file://AdditionalFile3627.zip?type=additional_file)

#3627. 「2021 集训队互测」这是一道集训队胡策题

标签: 传统 | 时间限制: 2000 ms | 内存限制: 1024 MiB |

题目描述

给出一个 $n×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$ 取模后的结果。

样例

输入

3
010
101
010

输出

2

数据范围与提示

对于全部数据，保证 $1≤n≤5000$，$0≤c_{i,j}≤1$。