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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#ifdef LOCAL
class SS {
   int x[0];
};
extern "C" SS __sanitizer_print_stack_trace();
#define __last_state                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                   \
   }                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                   \
   ;                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                   \
   SS x {                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                              \
      __sanitizer_print_stack_trace()
#endif

// #pragma GCC target("popcnt")
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define mp make_pair
#define st first
#define nd second
#define pii pair<int, int>
#define vi vector<int>
#define pb push_back
#define _upgrade ios_base::sync_with_stdio(0), cout.setf(ios::fixed), cout.precision(15), cin.tie(0), cout.tie(0);
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define fwd(i, a, b) for (int i = (a); i < (b); ++i)
#define trav(a, x) for (auto &a : x)
#define all(c) (c).begin(), (c).end()
#define sz(X) (int)((X).size())
typedef long double ld;
typedef unsigned long long ull;
typedef long long ll;
#ifdef LOCAL
ostream &operator<<(ostream &out, string str) {
   for (char c : str)
      out << c;
   return out;
}
template <class L, class R> ostream &operator<<(ostream &out, pair<L, R> p) { return out << "(" << p.st << ", " << p.nd << ")"; }
template <class L, class R, class S> ostream &operator<<(ostream &out, tuple<L, R, S> p) {
   auto &[a, b, c] = p;
   return out << "(" << a << ", " << b << ", " << c << ")";
}
template <class T> auto operator<<(ostream &out, T a) -> decltype(a.begin(), out) {
   out << '{';
   for (auto it = a.begin(); it != a.end(); it = next(it))
      out << (it != a.begin() ? ", " : "") << *it;
   return out << '}';
}
void dump() { cerr << "\n"; }
template <class T, class... Ts> void dump(T a, Ts... x) {
   cerr << a << ", ";
   dump(x...);
}
#define debug(...) cerr << "[" #__VA_ARGS__ "]: ", dump(__VA_ARGS__)
#else
#define debug(...) 42
#endif

const int MAXN = 9;

// array<array<array<ull, MAXN>, MAXN>, MAXN> arr
ull arr[9][9][9] = {{{0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0}},
                    {{0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 2, 0, 0, 0, 0, 0, 0, 0}, {0, 4, 4, 0, 0, 0, 0, 0, 0}, {0, 6, 12, 6, 0, 0, 0, 0, 0}, {0, 8, 24, 24, 8, 0, 0, 0, 0}, {0, 10, 40, 60, 40, 10, 0, 0, 0}, {0, 12, 60, 120, 120, 60, 12, 0, 0}, {0, 14, 84, 210, 280, 210, 84, 14, 0}},
                    {{0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 2, 0, 0, 0, 0, 0, 0, 0}, {0, 8, 16, 8, 0, 0, 0, 0, 0}, {0, 14, 56, 84, 56, 14, 0, 0, 0}, {0, 20, 120, 300, 400, 300, 120, 20, 0}, {0, 26, 208, 728, 1456, 1820, 1456, 728, 208}, {0, 32, 320, 1440, 3840, 6720, 8064, 6720, 3840}, {0, 38, 456, 2508, 8360, 18810, 30096, 35112, 30096}, {0, 44, 616, 4004, 16016, 44044, 88088, 132132, 151008}},
                    {{0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 4, 4, 0, 0, 0, 0, 0, 0}, {0, 14, 56, 84, 56, 14, 0, 0, 0}, {0, 24, 168, 504, 840, 840, 504, 168, 24}, {0, 34, 340, 1530, 4080, 7140, 8568, 7140, 4080}, {0, 44, 572, 3432, 12584, 31460, 56628, 75504, 75504}, {0, 54, 864, 6480, 30240, 98280, 235872, 432432, 617760}, {0, 64, 1216, 10944, 62016, 248064, 744192, 1736448, 3224832}, {0, 74, 1628, 17094, 113960, 541310, 1948716, 5521362, 12620256}},
                    {{0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 6, 12, 6, 0, 0, 0, 0, 0}, {0, 20, 120, 300, 400, 300, 120, 20, 0}, {0, 34, 340, 1530, 4080, 7140, 8568, 7140, 4080}, {0, 48, 672, 4368, 17472, 48048, 96096, 144144, 164736}, {0, 62, 1116, 9486, 50592, 189720, 531216, 1150968, 1973088}, {0, 76, 1672, 17556, 117040, 555940, 2001384, 5670588, 12961344}, {0, 90, 2340, 29250, 234000, 1345500, 5920200, 20720700, 59202000}, {0, 104, 3120, 45240, 422240, 2850120, 14820624, 61752600, 211723200}},
                    {{0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 8, 24, 24, 8, 0, 0, 0, 0}, {0, 26, 208, 728, 1456, 1820, 1456, 728, 208}, {0, 44, 572, 3432, 12584, 31460, 56628, 75504, 75504}, {0, 62, 1116, 9486, 50592, 189720, 531216, 1150968, 1973088}, {0, 80, 1840, 20240, 141680, 708400, 2691920, 8075760, 19612560}, {0, 98, 2744, 37044, 321048, 2006550, 9631440, 36920520, 116035920}, {0, 116, 3828, 61248, 632896, 4746720, 27530976, 128477888, 495557568}, {0, 134, 5092, 94202, 1130424, 9891210, 67260228, 369931254, 1691114304}},
                    {{0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 10, 40, 60, 40, 10, 0, 0, 0}, {0, 32, 320, 1440, 3840, 6720, 8064, 6720, 3840}, {0, 54, 864, 6480, 30240, 98280, 235872, 432432, 617760}, {0, 76, 1672, 17556, 117040, 555940, 2001384, 5670588, 12961344}, {0, 98, 2744, 37044, 321048, 2006550, 9631440, 36920520, 116035920}, {0, 120, 4080, 67320, 718080, 5565120, 33390720, 161388480, 645553920}, {0, 142, 5680, 110760, 1402960, 12977380, 93437136, 545049960, 2647385520}, {0, 164, 7544, 169740, 2489520, 26762340, 224803656, 1536158316, 8778047520}},
                    {{0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 12, 60, 120, 120, 60, 12, 0, 0}, {0, 38, 456, 2508, 8360, 18810, 30096, 35112, 30096}, {0, 64, 1216, 10944, 62016, 248064, 744192, 1736448, 3224832}, {0, 90, 2340, 29250, 234000, 1345500, 5920200, 20720700, 59202000}, {0, 116, 3828, 61248, 632896, 4746720, 27530976, 128477888, 495557568}, {0, 142, 5680, 110760, 1402960, 12977380, 93437136, 545049960, 2647385520}, {0, 168, 7896, 181608, 2724120, 29965320, 257701752, 1803912264, 10565771832}, {0, 194, 10476, 277614, 4811976, 61352694, 613526940, 5010470010, 34357508640}},
                    {{0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 14, 84, 210, 280, 210, 84, 14, 0}, {0, 44, 616, 4004, 16016, 44044, 88088, 132132, 151008}, {0, 74, 1628, 17094, 113960, 541310, 1948716, 5521362, 12620256}, {0, 104, 3120, 45240, 422240, 2850120, 14820624, 61752600, 211723200}, {0, 134, 5092, 94202, 1130424, 9891210, 67260228, 369931254, 1691114304}, {0, 164, 7544, 169740, 2489520, 26762340, 224803656, 1536158316, 8778047520}, {0, 194, 10476, 277614, 4811976, 61352694, 613526940, 5010470010, 34357508640}, {0, 224, 13888, 423584, 8471680, 124957280, 1449504448, 13770292256, 110162338048}}};

ull get_deg(ull n, ull m, ull mask, ull plansza, ull lewy, ull prawy) {
   auto dop = ~mask;
   auto dostepne = dop & plansza;
   return __builtin_popcountll((mask << n) & dostepne) + __builtin_popcountll((mask >> n) & dostepne) + __builtin_popcountll((mask << 1) & lewy & dostepne) + __builtin_popcountll((mask >> 1) & prawy & dostepne);
}

tuple<ull, ull, ull> get(int n, int m) {
   ull lewy = 0, prawy = 0, plansza = 0;
   rep(i, n * m) {
      lewy ^= ((ull)(i % n != 0)) << i;
      prawy ^= ((ull)(i % n != n - 1)) << i;
      plansza ^= ((ull)(1)) << i;
   }
   return {lewy, prawy, plansza};
}

typedef __uint128_t ulll;
// typedef ull ulll;

pair<ull, int> get_mask(int n, int m) {
   vector<string> s(m);
   rep(i, m) cin >> s[i];
   debug(s);
   ull mask = 0;
   ull par = 0;
   rep(i, m * n) if (s[i / n][i % n] == 'O') {
      par += (i / n) + i % n;
      mask ^= 1uLL << i;
   }
   return {mask, par % 2};
}

void pre() {
   fwd(n, 1, MAXN) fwd(m, 1, MAXN) fwd(k, 1, MAXN) if (k < n * m) {
      //   debug(n, m, k);
      auto [lewy, prawy, plansza] = get(n, m);
      debug(n, m, k, lewy, prawy, plansza);

      ulll x = 0;
      ulll bad = (ulll(1)) << (n * m);
      rep(i, k) x ^= (1 << i);

      while ((x & bad) == 0) {
         arr[n][m][k] += get_deg(n, m, x, plansza, lewy, prawy);
         auto c = x & -x, r = x + c;
         //  debug(x, c, r);
         x = (((r ^ x) >> 2) / c) | r;
      }
      assert(arr[n][m][k] % 2 == 0);
   }
   debug(arr);
}

int32_t main() {
   _upgrade;

   int m, n;
   cin >> m >> n;

   auto [_, par1] = get_mask(n, m);
   auto [mask, par2] = get_mask(n, m);

   if (par1 == par2) {
      auto [lewy, prawy, plansza] = get(n, m);
      auto deg = get_deg(n, m, mask, plansza, lewy, prawy);
      ld res = (ld)(deg) / (arr[n][m][__builtin_popcountll(mask)] / 2);
      cout << res << endl;
   } else {
      cout << 0 << endl;
   }
}