F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:祝各位Oier新年快乐,Rp++!
Problem 5095. -- 座位安排

5095: 座位安排

Time Limit: 6 Sec  Memory Limit: 256 MB
Submit: 53  Solved: 19
[Submit][Status][Discuss]

Description

小Q在家中举行了一场盛大的派对!他一共邀请了n-1个人,他家的圆桌上共有m个座位,每个座位只能坐一个人,
因此给这n个人(包括小Q自己)安排座位成为了一个麻烦。n个人依次编号为1到m,圆桌上m个座位顺时针依次编号为
1到m,m和1也是相邻的。每个人有着一些忌讳的数字,因此每个人都可能不喜欢坐在某些座位上。小Q希望大家不
感到拥挤,因此他不会让两个人坐在相邻的座位上;他还不会让大家面对面而感到尴尬,因此他不会让两个人正对
面坐下(当然如果只有奇数个座位,那么永远不可能正对面)。请写一个程序,帮助小Q计算合法的座位安排的方案
数,因为答案可能很大,请对998244353取模输出。

Input

第一行包含两个正整数n,m(2<=n<=10,4<=m<=1000),分别表示人数和座位数。

接下来n行,每行一个长度为m的01串g_i,其中g_{i,j}为1表示第i个人可以坐在座位j,为0表示不可以。

Output

输出一行一个整数,即合法方案数对998244353取模的结果。

Sample Input

3 6
110111
101101
110111

Sample Output

6

HINT
方案1:1坐在1,2坐在3,3坐在5。
方案2:1坐在5,2坐在3,3坐在1。
方案3:1坐在2,2坐在4,3坐在6。
方案4:1坐在2,2坐在6,3坐在4。
方案5:1坐在4,2坐在6,3坐在2。
方案6:1坐在6,2坐在4,3坐在2。

HINT

Source

[Submit][Status][Discuss]

HOME Back