845F - Guards In The Storehouse - CodeForces Solution

    
/*
⣿⣋⠥⠴⢲⡖⢒⡚⡳⣄⡰⠊⠁⢀⠄⡡⠋⠀⠀⠀⡀⠀⠀⠀⣼⠀⠀⠀⠙⣧⠀⠀⠀⠉⠻⣆⠀⠀⠀⠀⠀⠀⠉⠢⡀⠀⠀⠀⠐⣎⣻⣷⣶⣤⣀⣠⠴⣿⡦⠶⠦⣍⠻⣿⣿
⡭⠶⠒⢉⡽⠋⠉⢉⣷⡟⠁⠀⠢⠆⡜⣱⠀⠀⡰⣞⠁⠀⠀⡼⡏⠀⠀⠀⠀⢻⡆⠀⠀⠀⠀⠈⠄⠀⠀⠀⠀⠀⠀⠀⠈⠢⣄⠀⠀⢸⣿⣿⠿⣿⣿⡇⢰⠋⠀⢸⡆⠘⡷⢌⠻
⢀⣠⣴⠟⠁⢀⣴⠞⡽⠁⠀⠀⢀⡜⢰⠃⠀⣰⡵⠁⠀⢀⡾⠁⢀⠀⠀⠀⠀⠈⣿⠀⠀⠀⠀⠀⠐⡄⠀⠀⢠⡀⠀⠀⠀⠀⠙⣷⡄⠘⢿⡿⣿⣿⣿⢧⡘⢧⡀⠼⣇⡴⠃⠈⢳
⣾⣿⣿⣿⣿⡿⠃⢰⠃⠀⠀⢀⡾⢠⠃⠀⢰⡟⠁⠀⠀⣾⠃⠀⢸⢀⠀⠀⠀⠀⢹⡆⠀⠀⠀⠀⠀⠉⠹⡄⠀⠙⣄⠀⠀⠀⠀⠈⢟⣆⠀⢹⡉⢻⡘⣿⡳⣄⣩⣍⠉⠀⠀⠀⠀
⣿⣿⣿⣿⡟⢁⣀⡞⠀⠀⠀⣼⢃⡎⠀⠀⡿⠁⠀⠀⣸⡏⠀⠀⢸⠘⡄⠀⠀⠀⠀⠇⠀⠀⠀⠀⠀⠀⠀⢻⣄⠀⠈⢦⠀⠀⠀⠀⠈⢟⡆⠀⠱⡄⢳⡘⣿⣿⡟⠟⠀⠀⠀⠀⠀
⣿⣿⣿⡿⠚⠉⢠⡇⠀⠀⢰⡟⡸⠀⠀⢰⠃⠀⠀⢠⠟⠀⠀⠀⣾⠀⣷⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢧⠘⡏⢧⡀⠈⢧⠀⠀⠀⠀⠈⢻⠀⠀⠹⡄⢧⠈⢿⡇⠀⠀⠀⠀⠀⠀
⠙⣻⣿⣧⠀⠀⢸⠁⠀⠀⣾⠇⡇⠀⠀⡾⠀⠀⠀⠊⠀⠀⠀⡼⠉⣇⢿⣆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⡆⡇⠀⠙⣄⠈⢧⠀⠀⠀⠀⠈⠀⠀⠀⠸⡌⢷⣴⡛⢄⠀⠀⠀⠀⠀
⢀⣽⡏⢻⣇⠀⢸⢰⠃⢠⢿⢀⠇⠀⢠⡇⠀⠀⠀⢰⠀⠀⢰⠃⠀⠹⡸⣿⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣵⠀⠀⠈⢦⠈⢆⠀⠀⠀⠀⠀⠀⠈⢧⢱⡀⠳⣍⠓⠿⢦⠀⠀⠀
⡟⢡⣯⣄⠙⢦⢸⣼⠀⢸⢸⣸⠀⠀⢸⡇⠀⠀⢠⠄⠀⠀⡏⠀⠀⠀⢳⣯⠻⣄⠀⠀⢀⠀⠀⠀⠀⠀⡆⡟⣿⠀⠀⠀⠀⠳⡀⡄⠀⠀⠀⠀⠀⠀⢸⣧⣿⣷⢬⣷⣄⠀⠀⠀⠀
⠀⣼⣇⢩⠙⠚⠿⡇⠀⠘⠈⣿⡀⠀⡘⠁⠀⠀⠸⡇⠀⣸⠀⢀⣠⠤⠬⢿⡔⠛⢦⡀⢸⣺⠀⠀⠀⢀⣳⡇⢻⠈⠉⠑⠒⠤⣷⣸⠀⠀⠀⠀⠀⢀⣾⡙⣿⡼⡆⠀⠀⠀⠀⠀⠀
⢰⣿⣿⣎⢣⡀⠀⡇⠀⠀⠀⢹⡇⠀⡇⠀⠀⠀⠀⡇⢀⡏⠀⠀⠀⢀⡠⠜⣷⣀⡀⠙⢬⣿⣸⠀⠀⣸⣸⣠⢼⣭⣭⣤⣴⣦⡈⢿⡃⠀⠀⠘⡄⢸⡿⢇⢹⡷⣿⡀⢀⣀⣤⣤⣀
⢸⠁⣏⢻⡇⠀⣀⡇⠀⠀⠀⠈⣷⠀⠁⠀⠀⠀⠀⡇⢸⣶⣧⣴⣾⣿⣿⣿⣾⣮⠙⠀⢨⡟⢿⡄⣶⠏⢿⣽⣿⣿⣯⣿⣿⢿⣿⣿⡇⠀⠀⠀⣷⡘⣿⡸⣾⡇⠘⢷⣻⣿⣿⣿⠏
⠏⠀⢸⡌⢻⣦⡘⣧⢀⠀⠀⠀⠈⢧⡀⠀⠀⠀⠀⣸⣿⣿⣿⣽⣿⡽⠿⣭⣿⢿⡍⠳⣼⠃⠀⣟⣿⠃⠈⡏⠋⠛⣍⠙⣛⡷⣿⢊⣷⡆⠀⡆⡏⢳⣽⢣⡼⣷⡄⠈⢧⡀⠀⠀⠀
⠀⠀⢈⡿⣆⠙⢽⣿⣸⠀⡀⠀⠀⠀⢹⠀⠀⠀⠀⢻⣟⣛⠻⣇⠠⡀⠀⠈⠉⠻⣑⠄⠚⠳⠄⣿⠃⠱⣤⠆⠀⠳⡈⢦⠈⢿⣎⢻⣿⢠⡾⣿⣿⠀⠙⢿⣧⢳⠙⣦⡀⢻⣖⠦⠤
⠀⠀⠈⣿⡌⠀⠀⣇⣿⡆⣷⡀⠀⠀⢸⡇⠀⠘⣆⠀⢻⡄⠐⢮⡳⣌⠲⡀⠀⠀⠈⠂⠀⠀⠀⠉⠀⠀⠉⠀⠀⠀⠱⠀⠃⠀⠉⢻⡿⢻⣹⢿⣏⣇⠀⠀⠈⢿⣧⡘⡷⡄⢻⡀⠀
⠀⠀⠀⡏⣿⡄⢹⣿⠀⢧⣧⣣⢤⠀⠘⣷⠀⠀⢻⣷⣀⠹⣧⡀⠙⠮⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠋⠀⠘⣇⠸⣿⡼⡄⡆⠀⠘⣷⠱⣿⡙⣆⢳⠀
⠀⠀⢠⢇⡇⠘⡾⢹⠀⣸⣿⠹⣾⣧⡀⠘⣇⠰⡄⢷⠻⡓⢽⣦⠀⠀⠈⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣆⢻⡿⣄⢱⡀⠀⠸⡄⠈⠳⣜⡆⢇
⠀⠀⢸⣿⠁⠈⠁⢾⠄⡏⠙⣇⢹⡏⠳⣄⠘⢆⡿⣾⡆⠉⠦⠈⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡏⡿⢿⣷⠹⣦⣧⠀⠀⠹⣄⡀⠈⡇⢘
⠀⠀⣼⡇⠀⠀⠀⢸⢰⠃⠀⠈⠙⣗⠂⠈⠻⢾⣧⠈⠓⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⠔⠊⠙⠒⠀⠀⠀⠒⢲⡆⠀⠀⠀⠀⠀⠀⠀⢀⣾⡇⣷⠈⢿⣇⠈⢻⣧⠀⠀⢹⣍⢂⡇⠘
⠀⠀⢻⠀⠀⠀⠀⣼⡞⠀⠀⠀⠀⢹⢦⣀⣀⠘⠃⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠷⢤⣀⠠⠤⠤⠤⠤⠖⠈⠀⠀⠀⠀⠀⠀⠀⢠⣾⣿⣷⣿⠀⠸⣿⡆⠀⠹⣷⠀⠀⢻⡚⠀⠀
⠀⠰⠀⠀⠀⠀⢠⣿⠁⠀⢀⡇⠀⠸⣧⡈⠁⠀⣠⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣴⣿⣿⣿⣿⣿⠀⠀⣿⣿⡆⠀⢹⣇⠀⠀⢣⠔⠊
⠀⢠⠀⠀⠀⠀⣸⡏⠀⠀⢸⡇⠀⠸⣿⣿⢟⣿⣿⡿⣧⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⣾⣿⣿⣿⣿⣷⣿⠀⠀⣿⣿⣿⡄⢸⣿⡄⠀⠈⢇⠀
⠀⠀⠀⠀⡀⢀⡿⠀⠀⠀⡞⡇⠀⠀⣿⣿⣼⣿⣿⣧⣿⣿⣷⣦⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣴⣿⣿⣿⣿⣿⣿⣿⣿⠀⠀⣿⣿⣿⡇⣼⠟⠀⠀⠐⡜⡀
⠀⠂⠀⢰⡇⣸⠇⠀⠀⠀⡇⡇⠀⠀⣿⣿⣿⣿⣿⣿⣿⣿⣿⡌⠉⠑⠢⢤⣄⣀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠀⣠⣿⣿⠿⠛⠁⠀⠀⠀⠀⢹⣇
⠀⡀⠀⣾⡇⡿⠀⠀⠀⢘⣷⠇⠀⠀⢹⣿⣿⣿⣿⣿⣿⣿⠿⠧⠤⢤⣀⣀⠀⠉⠛⢿⣿⣶⣶⣤⣤⣤⣤⣴⣾⣿⣿⣿⣿⠿⠛⠉⢉⠻⣏⠙⠈⠉⠁⠀⠀⠀⠀⠀⣀⣠⡤⣿⠁
⢠⠇⣸⣿⣷⡇⠀⠀⢰⠀⠁⠀⣶⣚⣩⣋⡉⠙⠛⠿⣮⣄⡀⠀⠀⠀⠀⠈⠉⠓⠢⠤⣬⣝⡻⠿⠿⠿⠛⢻⣯⣀⠀⠈⢠⣖⣺⣿⣭⣍⣛⣓⣲⡤⢤⣤⣤⣤⡴⠾⣟⡻⠟⠛⠉
⣼⣰⣿⣿⣿⠁⣠⣤⣿⡀⣠⣴⣫⡽⠋⠀⠈⠙⡖⢤⣄⠉⠻⣶⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠉⠓⠲⠤⠤⠷⢬⡿⣶⣿⣿⣿⣿⣿⣿⣿⠋⠀⠀⠀⠀⠈⠀⠀⠀⠀⠉⠳⣄⠀
⠻⣿⣿⣿⠟⠉⠉⠀⠈⠉⠉⡿⠋⡴⠀⠀⠀⣸⠁⡇⠈⣳⢤⡀⠙⠿⣦⡀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⣤⣶⣿⡿⠛⠛⠛⠛⠛⠛⠛⠋⠉⠛⠲⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⣨⠟⠁⠀⠀⠀⠀⠀⢠⠎⠀⢠⠇⠀⠀⠀⠇⣸⠃⠀⠈⢦⠉⢲⣄⡈⠛⢷⣦⣤⣀⣠⣤⣴⠾⢛⣩⣴⣟⣉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⢧⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠞⠁⠀⠀⠀⠀⠀⠀⣰⢃⠀⠀⠸⠀⠀⠀⠀⠀⢿⡄⠀⠀⠀⢳⡀⢷⠙⠲⠤⢄⣈⣉⣩⠴⠖⠋⠉⠀⠀⠀⠈⠙⠲⢤⡀⠀⠀⠀⠀⠀⠀⠀⢠⠤⠬⢧⡀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠰⡃⢸⠀⠀⡇⠀⠀⠀⠀⠀⠸⡆⢀⡧⠀⠀⠓⠈⣆⠀⠀⠀⠀⣠⠊⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠳⣄⠀⠀⠀⠀⠀⠀⠀⠀⠸⣷⡀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⢀⣀⣀⣀⣸⡇⠈⡇⠀⠀⠀⠀⠀⠀⠀⠀⢟⠉⠀⠀⠀⠀⠀⠘⠀⠀⠀⡼⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠳⡀⠀⠀⠀⠀⠀⠀⠀⢱⢱⡀⠀⠀⠀⠀⠀⠀
⠀⠀⣀⡀⢙⣿⣿⣿⠿⡄⠸⠄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡞⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠱⡄⠀⠀⠀⠀⠀⠀⠈⣇⠱⡀⠀⠀⠀⠀⢀



──────▄▀▄─────▄▀▄
─────▄█░░▀▀▀▀▀░░█▄        aHR0cHM6Ly9lbW9qaWNvbWJvcy5jb20vYW5pbWUtYXNjaWktYXJ0
─▄▄──█░░░░░░░░░░░█──▄▄   
█▄▄█─█░░▀░░┬░░▀░░█─█▄▄█  



Copyright © 2023 deVICe . All rights reserved.                                            */

#include <bits/stdc++.h>
using namespace std;
#define int long long int
// #define push_back pb
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define MOD 1000000007

int n,m;
int a[251][251];
int dp[251][65536][2][2];
int gg(int pos,int mask,int f1, int f2)
{
    // cout<<pos<<" "<<mask<<" "<<f1<< " "<<f2<<"\n";
    if(pos%n==0){
        f1=0;
    }
    if(pos>=n*m)
    {
        // cout<<pos<<" "<<mask<<" "<<f1<< " "<<f2<<"\n";
        return 1;
    } 
    
    if(dp[pos][mask][f1][f2]!=-1) return dp[pos][mask][f1][f2];
    
    if(a[pos%n][pos/n]==1){
        // cout<<pos<<" "<<mask<<" "<<f1<< " "<<f2<<"\n";
        int mmask=mask;
        if((mask>>(pos%n))&1==1)
            mmask-=(1<<(pos%n));
        return dp[pos][mask][f1][f2]=gg(pos+1,mmask,0,f2);
    }
   
    int ans=0;
    ans+=gg(pos+1,mask|(1<<(pos%n)),1,f2);
    if(ans>=MOD)ans-=MOD;
    if(f1==0 && ((mask>>(pos%n))&1)==0)
    {
        if(f2==0) ans+=gg(pos+1,mask,f1,1);
        if(ans>=MOD)ans-=MOD;
        // else ans+=gg(pos+1,mask,f1,1);
    }
    else    
    if(f1!=0 || ((mask>>(pos%n))&1)!=0)
    {
        int mmask=mask;
        // if((mask>>(pos%n))&1==1)
        //     mmask-=(1<<(pos%n));
        ans+=gg(pos+1,mmask,f1,f2);
        if(ans>=MOD)ans-=MOD;
    }
    
    return dp[pos][mask][f1][f2]=ans;    
}


signed main()
{
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    IOS;
    
    cin>>n>>m;
    memset(dp,-1,sizeof dp);
    int f=0;
    if(n>m){
        // swap(n,m);
        f=1;
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            char c;
            cin>>c;
            if(f==0)
            {
                if(c=='.') a[i][j]=0;
                else a[i][j]=1;
            }
            else
            {
                if(c=='.') a[j][i]=0;
                else a[j][i]=1;
            }
        }
    }
    if(f)
        swap(n,m);
    // for(int i=0;i<n;i++)
    // {
    //     for(int j=0;j<m;j++)
    //     {
    //         cout<<a[i][j];
    //     }
    //     cout<<"\n";
    // }
    cout<<gg(0,0,0,0);
    
    

    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
    cin.clear();
    cin.get();
    return 0;
}