问题 2710 --czy的后宫1(摆花)

2710: czy的后宫1(摆花)

题目描述

  czy要妥善安排他的后宫,他想在机房摆一群妹子,一共有n个位置排成一排,每个位置可以摆妹子也可以不摆妹子。有些类型妹子如果摆在相邻的位置(隔着一个空的位置不算相邻),就不好看了。假定每种妹子数量无限,求摆妹子的方案数。

输入

输入有m+1行,第一行有两个用空格隔开的正整数n、m,m表示妹子的种类数。接下来的m行,每行有m个字符1或0,若第i行第j列为1,则表示第i种妹子第j种妹子不能排在相邻的位置,输入保证对称。(提示:同一种妹子可能不能排在相邻位置)。

输出

输出只有一个整数,为方案数(这个数字可能很大,请输出方案数除以1000000007的余数。

样例输入输出

输入#1 复制
2 2
01
10
输出#1 复制
7

提示

【样例说明】
七种方案为(空,空)、(空,1)、(1、空)、(2、空)、(空、2)、(1,1)、(2,2)。
【数据范围】
20%的数据,1<n≤5,0<m≤10。
60%的数据,1<n≤200,0<m≤100。
100%的数据,1<n≤1000000000,0<m≤100。

序号 标题 作者 发表时间 费用 订购数 操作