#P18546. Sticks

Sticks

Sticks

小青鱼有一个 n×nn\times n 的矩阵。每一行的左侧和每一列的上方各有一根木棍。令 xix_i 表示第 ii 行左侧木棍的长度,yiy_i 表示第 ii 列上方木棍的长度。所有长度都是 00 到 nn 之间的整数。

木棍必须互不相交。准确地说,不能存在 i,j∈[1,n]i,j\in[1,n],使 xi≥jx_i\ge j 和 yj≥iy_j\ge i 同时成立。

小青鱼据此定义一个 0101 矩阵 AA:对于每个 i,j∈[1,n]i,j\in[1,n],如果 xi≥jx_i\ge j 或 yj≥iy_j\ge i,则 Ai,j=1A_{i,j}=1;否则 Ai,j=0A_{i,j}=0。

现在给定一个由字符 0、1、? 组成的 n×nn\times n 矩阵 MM。将每个 ? 替换为 0 或 1,要求得到的矩阵至少能由一组满足上述条件的木棍长度 {x1,…,xn,y1,…,yn}\{x_1,\ldots,x_n,y_1,\ldots,y_n\} 产生。求可以得到多少个不同的矩阵,答案对 998244353998244353 取模。

同一个矩阵即使能由多组木棍产生,也只计一次。矩阵的行、列编号均从 11 开始。

输入格式

第一行一个整数 nn,满足 1≤n≤30001\le n\le3000。

接下来 nn 行,每行一个长度为 nn 的字符串,仅包含 0、1 和 ?,描述矩阵 MM。

本题输入只包含一个矩阵,没有测试组数 TT。

输出格式

输出一行一个整数,表示不同合法矩阵的数量对 998244353998244353 取模的结果。

样例 1

2
??
??
14

样例 2

5
??1??
?1??0
??0??
???1?
??1??
3144

样例 3

10
0000000000
??????????
??????????
??????????
??????????
??????????
??????????
??????????
??????????
??????????
361458985