1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
using namespace std;

#define FOR(i, b, e) for(int i = (b); i < (e); i++)
#define TRAV(x, v) for(auto &x: v)
#define PB push_back
#define SZ(x) ((int)x.size())
#define X first
#define Y second

using ll = long long;
using vi = vector<int>;
using ii = pair<int, int>;
constexpr int INF = 0x3f3f3f3f;

using K = long double;
constexpr K EPS = 1e-17;
map<unsigned long long, int> boardNumber;

int n, m;

void prepMap(vector<vi> board) {
    int cnt = 0;
    TRAV(x, board) cnt += count(x.begin(), x.end(), 1);
    vi vec(n * m);
    FOR(i, 0, cnt) vec[SZ(vec) - 1 - i] = 1;
    int id = 0;
    do
    {
        unsigned long long newBoard = 0;
        FOR(i, 0, n) FOR(j, 0, m) newBoard ^= (1ull * vec[i * m + j]) << (i * m + j);
        boardNumber[newBoard] = id++;
    } while (next_permutation(vec.begin(), vec.end()));
}

vector<vi> readBoard() {
    vector<vi> res(n, vi(m));
    FOR(i, 0, n) {
        string s;
        cin >> s;
        FOR(j, 0, m) res[i][j] = s[j] == 'O';
    }
    return res;
}

bool ok(int i, int j) {
    return 0 <= i && i < n && 0 <= j && j < m;
}

bool bit(int i, int j, unsigned long long board) {
    return (board >> (i * m + j)) & 1ull;
}

vi getNeighbours(unsigned long long board) {
    vi neigh;
    int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};
    FOR(i, 0, n) FOR(j, 0, m) if(bit(i, j, board)) {
        FOR(k, 0, 4) {
            int ni = i + dx[k], nj = j + dy[k];
            if(ok(ni, nj) && !bit(ni, nj, board)) {
                unsigned long long newboard = board;
                newboard ^= 1ull << (i * m + j);
                newboard ^= 1ull << (ni * m + nj);
                neigh.PB(boardNumber[newboard]);
            }
        }
    }
    sort(neigh.begin(), neigh.end());
    neigh.erase(unique(neigh.begin(), neigh.end()), neigh.end());
    return neigh;
}

unsigned long long conv(vector<vi> board) {
    unsigned long long res = 0;
    FOR(i, 0, n) FOR(j, 0, m) res ^= (1ull * board[i][j]) << (i * m + j);
    return res;
}

int parity(vector<vi> board) {
    int res = 0;
    FOR(i, 0, n) FOR(j, 0, m) if(board[i][j]) res = (res + i + j) % 2;
    return res;
}

void solve() {
    cin >> n >> m;
    cout << fixed << setprecision(15);
    vector<vi> startBoard = readBoard();
    vector<vi> endBoard = readBoard();
    if(parity(startBoard) != parity(endBoard)) {
        cout << 0 << '\n';
        return;
    }
    prepMap(startBoard);
    vector<vi> G(SZ(boardNumber));
    TRAV(x, boardNumber) G[x.Y] = getNeighbours(x.X);
    vector<K> ans(SZ(boardNumber));
    ans[boardNumber[conv(startBoard)]] = 1;
    vector<K> parAns = ans;
    int it = 1;
    while(it++) {
        vector<K> newAns(SZ(G));
        FOR(i, 0, SZ(G)) TRAV(x, G[i]) newAns[i] += ans[x] / SZ(G[x]);
        ans = newAns;
        if(it & 1) {
            bool close = 1;
            FOR(i, 0, SZ(ans)) close &= abs(ans[i] - parAns[i]) < EPS;
            if(close) break;
            parAns = ans;
        }
    }
    cout << ans[boardNumber[conv(endBoard)]] << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    // int tt; cin >> tt;
    // FOR(te, 0, tt) {
    //     // cout << "Case #" << te + 1 << ": ";
    //     solve();
    // }
    solve();
    return 0;
}