1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define maxn 1000 5 using namespace std; 6 const int mod= 100000000; 7  8 int dp[500][maxn]; 9 int n,m,t1;10 int s[500],a[maxn];11 12 void inti()13 {14     t1=0;15     for(int i=0; i<(1<<n); i++)16     {17         if((i&(i<<1))==0)18         {19             s[t1++]=i;20         }21     }22 }23 24 int main()25 {26     while(scanf("%d%d",&m,&n)!=EOF)27     {28         inti();29         for(int i=0; i<m; i++)30         {31             a[i]=0;32             for(int j=0; j<n; j++)33             {34                 int c;35                 scanf("%d",&c);36                 a[i]+=(c<<j);37             }38         }39         memset(dp,0,sizeof(dp));40         for(int i=0; i<t1; i++)41         {42             if((a[0]&s[i])==s[i])43             {44                 dp[0][i]=1;45             }46         }47         for(int i=1; i<m; i++)48         {49             for(int j=0; j<t1; j++)50             {51                 if((a[i]&s[j])==s[j])52                 {53                     for(int k=0; k<t1; k++)54                     {55                         if((s[j]&s[k])==0&&dp[i-1][k]!=0)56                         {57                             dp[i][j]=(dp[i][j]+dp[i-1][k])%mod;58                         }59                     }60                 }61             }62         }63         int ans=0;64         for(int i=0; i<t1; i++)65         {66             if(dp[m-1][i]!=0)67             {68                 ans=(ans+dp[m-1][i])%mod;69             }70         }71         printf("%d\n",ans);72     }73     return 0;74 }