1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #define mod 100000000 5 using namespace std; 6 int dp[13][1<<12],cur[13]; 7 int can[1<<12],tot,m,n; 8 int main() 9 { 10 while(~scanf("%d%d",&m,&n)) 11 { 12 tot = 0; 13 for(int i=0;i<(1<<n);i++) 14 if((i&(i<<1))==0) can[tot++] = i; 15 memset(cur,0,sizeof(cur)); 16 memset(dp,0,sizeof(dp)); 17 for(int i=1;i<=m;i++) 18 { 19 for(int j=0;j<n;j++) 20 { 21 int num; 22 scanf("%d",&num); 23 if(num==0) cur[i] = (cur[i]|(1<<j)); 24 } 25 } 26 for(int i=0;i<tot;i++) 27 if((cur[1]&can[i])==0) dp[1][can[i]] = 1; 28 for(int i=1;i<m;i++) 29 { 30 for(int j=0;j<tot;j++) 31 { 32 if((can[j]&cur[i])==0) 33 { 34 for(int k=0;k<tot;k++) 35 { 36 if(((can[k]&cur[i+1])==0)&&((can[k]&can[j])==0)) 37 dp[i+1][can[k]] = dp[i+1][can[k]]+dp[i][can[j]]; 38 } 39 } 40 } 41 } 42 int ans = 0; 43 for(int i=0;i<tot;i++) 44 { 45 ans += dp[m][can[i]]; 46 ans = ans % mod; 47 } 48 printf("%d ",ans); 49 } 50 }