dsa hw5

#include <bits/stdc++.h>
using namespace std;
#define REP(i, j, k)  for(int i = j; i <  k; ++i)
#define IOS cin.tie(0) , cout.sync_with_stdio(0)
#define endl "\n"
///------------------------------------------------------------
#define MAX 11
#define mod 1000000007LL

int n , m;
int c[MAX * MAX][MAX * MAX] , I[MAX][MAX] , _[MAX][MAX];
int dp[MAX][MAX][MAX][MAX][MAX * MAX];
string s[MAX];

inline void U(int &now , int val){
    now += val;
    if(now >= mod) now -= mod;
}
int DP(int l , int r , int a , int b , int k){
    if(dp[l][r][a][b][k] != -1) return dp[l][r][a][b][k];
    if(k == 0) return 1;
    if(l > r || a > b) return 0;

    int &now = dp[l][r][a][b][k];
    now = 0;

    REP(i , l , r + 1) if(_[i][b] - _[i][a - 1] == 0){
        if(i == l && i == r) continue;
        else if(i == l) U(now , DP(i + 1 , r , a , b , k - 1));
        else if(i == r) U(now , DP(l , i - 1 , a , b , k - 1));
        else {
            REP(ii , 0 , k){
                int v1 = DP(l , i - 1 , a , b , ii);
                int v2 = DP(i + 1 , r , a , b , k - 1 - ii);
                U(now , 1ll * c[k - 1][ii] * v1 % mod * v2 % mod);
           }
        }
    }
    REP(i , a , b + 1) if(I[r][i] - I[l - 1][i] == 0){
        if(i == a && i == b) continue;
        else if(i == a) U(now , DP(l , r , i + 1 , b , k - 1));
        else if(i == b) U(now , DP(l , r , a , i - 1 , k - 1));
        else {
            REP(ii , 0 , k){
                int v1 = DP(l , r , a , i - 1 , ii);
                int v2 = DP(l , r , i + 1 , b , k - 1 - ii);
                U(now , 1ll * c[k - 1][ii] * v1 % mod * v2 % mod);
            }
        }
    }
    return now;
}
int32_t main(){
    IOS;
    cin >> n >> m;
    REP(i , 0 , n) cin >> s[i];

    memset(dp , -1 , sizeof dp);

    REP(i , 1 , n + 1) REP(j , 1 , m + 1) I[i][j] = (s[i - 1][j - 1] == 'X' ? 1 : 0);
    REP(i , 1 , n + 1) REP(j , 1 , m + 1) I[i][j] += I[i - 1][j];

    REP(i , 1 , n + 1) REP(j , 1 , m + 1) _[i][j] = (s[i - 1][j - 1] == 'X' ? 1 : 0);
    REP(i , 1 , n + 1) REP(j , 1 , m + 1) _[i][j] += _[i][j - 1];

    REP(i , 0 , MAX * MAX) REP(j , 0 , i + 1){
        if(j == 0 || j == i) c[i][j] = 1;
        else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
    }

    int ans = 0;
    REP(i , 0 , n * m + 1) U(ans , DP(1 , n , 1 , m , i));

    cout << ans << endl;
    return 0;
}