#include <iostream>

 #include <cstdio>

 #include <cmath>

 #include <vector>

 #include <cstring>

 #include <string>

 #include <algorithm>

 #include <string>

 #include <set>

 #include <functional>

 #include <numeric>

 #include <sstream>

 #include <stack>

 //#include <map>

 #include <queue>

 #include <deque>

 //#pragma comment(linker, "/STACK:102400000,102400000")

 #define CL(arr, val)    memset(arr, val, sizeof(arr))

 #define ll long long

 #define INF 0x7f7f7f7f

 #define lc l,m,rt<<1

 #define rc m + 1,r,rt<<1|1

 #define pi acos(-1.0)

 #define L(x)    (x) << 1

 #define R(x)    (x) << 1 | 1

 #define MID(l, r)   (l + r) >> 1

 #define Min(x, y)   (x) < (y) ? (x) : (y)

 #define Max(x, y)   (x) < (y) ? (y) : (x)

 #define E(x)        (1 << (x))

 #define iabs(x)     (x) < 0 ? -(x) : (x)

 #define OUT(x)  printf("%I64d\n", x)

 #define lowbit(x)   (x)&(-x)

 #define Read()  freopen("a.txt", "r", stdin)

 #define Write() freopen("b.txt", "w", stdout);

 #define maxn 110

 #define maxv 5010

 #define mod 1000000000

 using namespace std;

 int n,m,top=;

 int state[],num[];

 int dp[][]; //最多是600个状态,不知道是以什么方式算出来的

 int cur[];

 inline bool ok(int x) //判断同一行是否有相邻的1

 {

     if(x&x<<) return ;

     return ;

 }

 void init() //初始化 2^m个状态,把有相邻1的状态的去掉

 {

     top=;

     int total=<<m;

     for(int i=;i<total;i++)

         if(ok(i)) state[++top]=i;

 }

 inline bool fit(int x,int k) //判断状态x和读入的第k行是否冲突,注意cur[k]中1代表不能种,

 {                            //所以只要相与为1则表示不行

     if(x&cur[k]) return ;

     return ;

 }

 int main()

 {

     //Read();

     while(~scanf("%d%d",&n,&m))

     {

         init();

         memset(dp,,sizeof(dp));

         for(int i=;i<=n;i++)

         {

             cur[i]=;

             int num;

             for(int j=;j<=m;j++) //这里是为0表示可以种,为1表示是不可以种

             {                     //注意和上面区分,这里主要是为了判断冲突.

                 scanf("%d",&num);

                 if(!num) cur[i]+=(<<(m-j));//把每一行转换成2进制,并用cur存储

             }

             //printf("%d\n",cur[i]);

         }

         for(int i=;i<=top;i++) //初始化第一行,

         {

             if(fit(state[i],)) //不冲突表示可以放

                 dp[][i]=;

         }

         for(int i=;i<=n;i++)

         {

             for(int j=;j<=top;j++)

             {

                 if(!fit(state[j],i)) continue; //判断第i行和读入的图是否冲突

                 for(int k=;k<=top;k++)

                 {

                     if(!fit(state[k],i-)) continue; //判断第i-1行是否冲突

                     if(state[j]&state[k]) continue;//判断第i行和第i-1行是否冲突

                     dp[i][j]=(dp[i][j]+dp[i-][k])%mod;

                 }

             }

         }

         int ans=;

         for(int i=;i<=top;i++)

         {

             ans=(ans+dp[n][i])%mod;

         }

         printf("%d\n",ans);

     }

     return ;

 }