#include<bits/stdc++.h> using namespace std; #define ll long long bool AAA; const int MAXN=310,N=17,M=150,Mod=1e9+7; int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();return x*f;} void add(int &x,int y){x+=y;if(x>=Mod)x-=Mod;} int n,m,fl,a[MAXN][MAXN],as[MAXN][MAXN],f[(1<<N)+10][2],g[(1<<N)+10][2]; int F[M][(1<<N)+10][2],G[M][(1<<N)+10][2]; void DP(int x,int y){ for(int s=0;s<1<<m;s++){ if((s>>y&1)&&x&&a[x][y]==a[x-1][y])add(g[s][0],f[s][1]),add(g[s][0],f[s][0]); if(y&&a[x][y]==a[x][y-1])add(g[(s|(1<<y)|(1<<y-1))^(1<<y)^(1<<y-1)][1],f[s][1]); add(g[s|(1<<y)][1],f[s][0]); add(g[s|(1<<y)][1],f[s][1]); } } void DP2(int x,int y){ for(int s=0;s<1<<m;s++){ if((s>>y&1)&&x+1<n&&a[x][y]==a[x+1][y])add(g[s][0],f[s][1]),add(g[s][0],f[s][0]); if(y+1<m&&a[x][y]==a[x][y+1])add(g[(s|(1<<y)|(1<<y+1))^(1<<y)^(1<<y+1)][1],f[s][1]); add(g[s|(1<<y)][1],f[s][0]); add(g[s|(1<<y)][1],f[s][1]); } } void sol(int l,int r){ for(int s=0;s<1<<m;s++)f[s][0]=f[s][1]=0; f[0][0]=1; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ int o=i*m+j; if(o>=l&&o<=r){ a[i][j]^=1; DP(i,j); for(int s=0;s<1<<m;s++)F[o-l][s][0]=g[s][0],F[o-l][s][1]=g[s][1],g[s][0]=g[s][1]=0; a[i][j]^=1; } DP(i,j); for(int s=0;s<1<<m;s++)f[s][0]=g[s][0],f[s][1]=g[s][1],g[s][0]=g[s][1]=0; } for(int s=0;s<(1<<m);s++)add(f[s][0],f[s][1]),f[s][1]=0; } for(int s=0;s<1<<m;s++)f[s][0]=f[s][1]=0; f[0][0]=1; for(int i=n-1;i>=0;i--){ for(int j=m-1;j>=0;j--){ int o=i*m+j; if(o>=l&&o<=r)for(int s=0;s<1<<m;s++)G[o-l][s][0]=f[s][0],G[o-l][s][1]=f[s][1]; DP2(i,j); for(int s=0;s<1<<m;s++)f[s][0]=g[s][0],f[s][1]=g[s][1],g[s][0]=g[s][1]=0; } for(int s=0;s<(1<<m);s++)add(f[s][0],f[s][1]),f[s][1]=0; } for(int s=0;s<1<<m;s++)f[s][0]=f[s][1]=0; for(int o=l;o<=r;o++){ int i=o/m,j=o%m; a[i][j]^=1; for(int s=0;s<1<<m;s++)if(s>>j&1){ add(F[o-l][s^(1<<j)][0],F[o-l][s][0]); add(F[o-l][s^(1<<j)][0],F[o-l][s^(1<<j)][1]); add(F[o-l][s^(1<<j)][0],F[o-l][s][1]); add(F[o-l][s^(1<<j)][1],F[o-l][s][1]); add(F[o-l][s][0],F[o-l][s][1]); F[o-l][s][1]=0; if(j+1==m||a[i][j]!=a[i][j+1])F[o-l][s^(1<<j)][1]=0; if(i+1==n||a[i][j]!=a[i+1][j])F[o-l][s][0]=0; } if(j+1!=m){ j++; for(int s=0;s<1<<m;s++)if(s>>j&1){ add(G[o-l][s^(1<<j)][0],G[o-l][s][0]); add(G[o-l][s^(1<<j)][0],G[o-l][s^(1<<j)][1]); add(G[o-l][s^(1<<j)][0],G[o-l][s][1]); add(G[o-l][s^(1<<j)][1],G[o-l][s][1]); add(G[o-l][s][0],G[o-l][s][1]); G[o-l][s][1]=0; if(!j||a[i][j]!=a[i][j-1])G[o-l][s^(1<<j)][1]=0; if(!i||a[i][j]!=a[i-1][j])G[o-l][s][0]=0; } j--; } for(int e=0;e<m;e++)if(e!=j){ for(int s=(1<<m)-1;s>=0;s--)if((s>>e&1)){ int p=i-(e>j); add(F[o-l][s^(1<<e)][0],F[o-l][s][0]),add(F[o-l][s^(1<<e)][1],F[o-l][s][1]); if(p+1==n||a[p][e]!=a[p+1][e])F[o-l][s][0]=F[o-l][s][1]=0; } } for(int e=0;e<m;e++)if(e!=j+1){ for(int s=(1<<m)-1;s>=0;s--)if((s>>e&1)){ int p=i-(e>j); add(G[o-l][s^(1<<e)][0],G[o-l][s][0]),add(G[o-l][s^(1<<e)][1],G[o-l][s][1]); if(p+1==n||a[p][e]!=a[p+1][e])G[o-l][s][0]=G[o-l][s][1]=0; } } for(int s=0;s<1<<m;s++) add(as[i][j],(ll)F[o-l][s][0]*G[o-l][s][0]%Mod),add(as[i][j],(ll)F[o-l][s][1]*G[o-l][s][1]%Mod); a[i][j]^=1; } } void slv(){ n=read(),m=read(); for(int i=0;i<n;i++) for(int j=0;j<m;j++){ char c=getchar();while(c!='0'&&c!='1')c=getchar(); if(m<=n)a[i][j]=c-'0';else a[j][i]=c-'0'; } if(m>n)swap(n,m),fl=1; for(int l=0;l<n*m;l+=M)sol(l,min(l+M-1,n*m-1)); if(fl)swap(n,m); for(int i=0;i<n;i++,puts("")) for(int j=0;j<m;j++) if(m<=n)printf("%d ",as[i][j]); else printf("%d ",as[j][i]); } bool BBB; signed main(){ // freopen("1.in","r",stdin);freopen("1.out","w",stdout); slv(); // cerr<<clock()*1.0/CLOCKS_PER_SEC<<"s\n"; // cerr<<((&AAA)-(&BBB))/1024.0/1024<<"MB\n"; return 0; }