牧场的安排

内存限制：512 MiB

时间限制：1000 ms

原题来自：USACO 2006 Nov. Gold

Farmer John 新买了一块长方形的牧场，这块牧场被划分成 MMM 行 NNN 列 $(1\le M\le 12;1\le N\le 12)，每一格都是一块正方形的土地。FJ\; 打算在牧场上的某几格土地里种上美味的草，供他的奶牛们享用。遗憾的是，有些土地相当的贫瘠，不能用来放牧。并且，奶牛们喜欢独占一块草地，于是\; FJ\; 不会选择两块相邻的土地，即：没有哪两块草地有公共边。当然，FJ\; 还没有决定在哪些土地上种草。$

作为一个好奇的农场主，FJ 想知道，如果不考虑草地的总块数，那么，一共有多少种种植方案可供他选择。当然，把新的牧场荒废，不在任何土地上种草，也算一种方案。请你帮 FJ 算一下这个总方案数。

输入格式

第 111 行：两个正整数 MMM 和 NNN，用空格隔开；

第 222 到 M+1M+1M+1 行：每行包含 NNN 个用空格隔开的整数，描述了每块土地的状态。输入的第 i+1i+1i+1 行描述了第 iii 行的土地。所有整数均为 000 或 111，111 表示这块土地足够肥沃，000 则表示这块地上不适合种草。

输出格式

第 111 行：输出一个整数，即牧场分配总方案数除以 10810^810​8​​ 的余数。

样例

样例输入

2 3  1 1 1  0 1 0

样例输出

9 -------------------------------------------------------------------------------------------------- 状态压缩动态规划 首先处理出所有行的复合要求的养牛的状态，

(s&cd[i])==s && (s&(s<<1))==0，也就是当前养牛的场地都在有草的地方且养牛的地点不相邻 让后状压动归，f[i][s]表示到第i行，且第i行的状态为s的情况下有多少种方案。 f[i][s]+=f[i-1][ss]，条件s和ss都是对应的行内的合法状态，且两者之间的关系合法，也就是s&ss==0

--------------------------------------------------------------------------------------------------

1 #include
          
            2 using namespace std; 3 typedef long long ll; 4 int n,m; 5 vector
           
            st[14]; 6 int cd[14]; 7 ll f[14][(1<<12)+5]; 8  9 void getst()10 {11     st[0].push_back(0);12     for(int i=1;i<=n;++i)13     {14         for(int s=0;s<(1<