# pragma GCC optimize(2)
//#include<ctime>
#include<cstdio>
#include<cstring>
using namespace std;
int g[16][16][16][16],f[20][20][65536];
char ch[16][16];
int*F,*G;
void _(int&a,int b){(a+=b)>=19901013?a-=19901013:0;}
int main(){
    int n,m;scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%s",ch[i]+1);//printf("%d\n",clock());
    for(int l=1;l<=m;l++)for(int r=l;r<=m;r++)for(int u=1;u<=n;u++){
        int O=1<<r-l+1;--O;
        G=f[u][l];*G=1;
        memset(G+1,0,O<<2);
        for(int i=u;i<=n;//printf("g[%d][%d][%d][%d]=%d\n",u,i,l,r,g[u][i][l][r]),
        i++)for(int j=l;j<=r;j++){
            F=G;G=j==r?f[i+1][l]:f[i][j+1];
            memset(G,0,(O<<2)+4);
            int x=1<<r-j,c1=ch[i][j],c2=ch[i][j-1],c3=ch[i-1][j];
            for(int k=0,*Fk=F;k<=O;k++,Fk++){
                if(!*Fk)continue;
                _(G[k&~(x)],*Fk);
                if(j>l&&c2&2&&c1&2&&!(k&(x+x)))_(G[k|(x+x+x)],*Fk);
                if(i>u&&c3&2&&c1&2&&!(k&(x)))_(G[k|(x)],*Fk);
            }if(j==r)for(int k=0,*Gk=G;k<=O;k++,Gk++)_(g[u][i][l][r],*Gk);
            //for(int k=0;k<=O;k++)G[k]=0;
            //for(int k=0;k<=O;k++)printf("G[%d]=%d F[%d]=%d i=%d j=%d\n",k,G[k],k,F[k],i,j);
        }
    }//printf("%d,%d\n",g[1][n][1][m],clock());puts("");
    long long ans=0,tmp=0,g[16]={0};
    for(int i=0;i<(1<<m);i+=2){
        int t=0,o[16];
        o[0]=0;
        for(int j=1;j<m;j++)if(i&(1<<j))o[++t]=j;
        o[++t]=m;
        for(int d=1;d<=n;d++)for(int u=1;u<=d;u++){
            tmp=1;
            for(int i=1;i<=t;i++)tmp=tmp*::g[u][d][o[i-1]+1][o[i]]%19901013;
            if(u==1)g[d]=tmp;else g[d]=(g[d]+(19901013-tmp)*g[u-1])%19901013;
        }ans+=t&1?g[n]:19901013-g[n];if(ans>19901012)ans-=19901013;
    }printf("%d\n",(int)ans);
}

绝对良心

暴力DP只能拿70分。。。查了报告。。用容斥原理才能搞定。。。

没有希望了，太变态了

jiayou

这是一道天牛题，不是我能做的....

观望天牛AC吧....

这题是YHC天牛出的，是今年浙江省选最后一题，做出来的应该一部分是标程

我也不会.

不会......标程太长了......

貌似 状态压缩dp+容斥原理

只有80分捏。。不是7秒么

Orz..

Orz，太牛×了，不会做。

虽然提交题目的人很牛，能过7个点...

不过VJ不是要交标程能过才能放题吗

看了xys的题解……太难了。。

回楼下，那个twb是假的，他是宋神牛！！！！！！！！！

下面的TWB神牛说说我也会，你过了吗？怎一个B字了得，我看你是假冒的吧，真正的twb神牛应该很modest

很好玩哦~

打表吧~

---|闪---|

楼下的楼下的楼下的楼下是假的。

都是标程

囧rz，我写出来的程序虽然只有2.3KB，但是巨慢：

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 290ms

├ 测试数据 06：答案正确... 727ms

├ 测试数据 07：答案正确... 306ms

├ 测试数据 08：答案正确... 1210ms

├ 测试数据 09：答案正确... 1897ms

├ 测试数据 10：答案正确... 4408ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：8838ms