Problem 3 czy的后宫(harem.cpp/c/pas)
【题目描述】
czy要妥善安排他的后宫，他想在机房摆一群妹子，一共有n个位置排成一排，每个位置可以摆妹子也可以不摆妹子。有些类型妹子如果摆在相邻的位置（隔着一个空的位置不算相邻），就不好看了。假定每种妹子数量无限，求摆妹子的方案数。
【输入格式】
输入有m+1行，第一行有两个用空格隔开的正整数n、m，m表示妹子的种类数。接下来的m行，每行有m个字符1或0,若第i行第j列为1，则表示第i种妹子第j种妹子不能排在相邻的位置，输入保证对称。（提示：同一种妹子可能不能排在相邻位置）。
【输出格式】
输出只有一个整数，为方案数（这个数字可能很大，请输出方案数除以1000000007的余数。
【样例输入】
2 2
01
10
【样例输出】
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。
注：此题时限1.5s是因为本评测机跑太慢，大家正常做
但写的太丑可能T一俩个点

source:hzwer