P3711摆花 | ||
|
问题描述
艺术馆门前将摆出许多花,一共有n个位置排成一排,每个位置可以摆花也可以不摆花。有些花如果摆在相邻的位置(隔着一个空的位置不算相邻),就不好看了。假定每种花数量无限,求摆花的方案数。
输入格式
输入共有1+m行:
第一行有两个用空格隔开的正整数n、m,m表示花的种类数。
接下来的m行,每行有m个字符1或0,若第i行第j列为1,则表示第i种花和第j种花不能排在相邻的位置,输入保证对称。(提示:同一种花可能不能排在相邻位置)。
输出格式
输出只有一个整数,为方案数(这个数字可能很大,请输出方案数除以1000000007的余数)
样例输入 1
2 2
0 1
1 0
样例输出 1
7
样例输入 2
3 3
0 0 0
0 1 0
0 0 1
样例输出 2
50
提示
样例说明
七种方案为(空,空)、(空,1)、(1、空)、(2、空)、(空、2)、(1,1)、(2,2)
100%的数据,1<n≤1000000000,0<m≤100。
来源 CH Round#30