状态压缩：玉米田

农夫约翰的土地由 M×NM×N 个小方格组成，现在他要在土地里种植玉米。

非常遗憾，部分土地是不育的，无法种植。

而且，相邻的土地不能同时种植玉米，也就是说种植玉米的所有方格之间都不会有公共边缘。

现在给定土地的大小，请你求出共有多少种种植方法。

土地上什么都不种也算一种方法。

输入格式

第 11 行包含两个整数 MM 和 NN。

第 2..M+12..M+1 行：每行包含 NN 个整数 00 或 11，用来描述整个土地的状况，11 表示该块土地肥沃，00 表示该块土地不育。

输出格式

输出总种植方法对 108108 取模后的值。

数据范围

1≤M,N≤121≤M,N≤12

输入样例：

2 3
1 1 1
0 1 0

输出样例：

9

代码如下：

#include 

using namespace std;
const int N=14,mod=1e9;
int g[N];//
int dp[N][1< a[1<>n>>m;
    int b;
    for(int i=0;i>b;
            g[i]=(g[i]<<1)+b;
        }
    for(int i=0;i<1<>1))==0);

    for(int i=1;i<=n+1;i++)
    {
        for(int j=0;j<1<0)) break;//第i+1行只用到状态为0的情况，因为没有i+1行。
            if(((j&g[i-1])==j)&&h[j])
            for(int k=0;k