#P18546. Sticks
Sticks
Sticks
小青鱼有一个 的矩阵。每一行的左侧和每一列的上方各有一根木棍。令 表示第 行左侧木棍的长度, 表示第 列上方木棍的长度。所有长度都是 到 之间的整数。
木棍必须互不相交。准确地说,不能存在 ,使 和 同时成立。
小青鱼据此定义一个 矩阵 :对于每个 ,如果 或 ,则 ;否则 。
现在给定一个由字符 0、1、? 组成的 矩阵 。将每个 ? 替换为 0 或 1,要求得到的矩阵至少能由一组满足上述条件的木棍长度 产生。求可以得到多少个不同的矩阵,答案对 取模。
同一个矩阵即使能由多组木棍产生,也只计一次。矩阵的行、列编号均从 开始。
输入格式
第一行一个整数 ,满足 。
接下来 行,每行一个长度为 的字符串,仅包含 0、1 和 ?,描述矩阵 。
本题输入只包含一个矩阵,没有测试组数 。
输出格式
输出一行一个整数,表示不同合法矩阵的数量对 取模的结果。
样例 1
2
??
??
14
样例 2
5
??1??
?1??0
??0??
???1?
??1??
3144
样例 3
10
0000000000
??????????
??????????
??????????
??????????
??????????
??????????
??????????
??????????
??????????
361458985