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
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
#include <cstdio>
#include <cstdint>
#include <vector>

using namespace std;

int n, m;

typedef vector<vector<bool> > board_t;

// perl script used to precalculate totals

/*
#!/usr/bin/perl
use Modern::Perl '2010';
use Data::Dumper;

for my $n (1 .. 8) {
	for my $m (1 .. 8) {
		for my $k (1 .. 8) {
			for my $par (0, 1) {
				print calculate($n, $m, $k, $par), 'LL, ';
			}
		}
		say "";
		print "\t";
	}
}


sub _binomial {
	my ($n, $k) = @_;
	return 0 if $k < 0;
	return 0 if $k > $n;
	my $ret = 1;
	for my $i ($n - $k + 1 .. $n) {
		$ret *= $i;
	}
	for my $i (2 .. $k) {
		$ret /= $i;
	}
	$ret;
}

my %binomials = ();
sub binomial {
	my ($n, $k) = @_;
	my $key = "$n:$k";
	return $binomials{$key} if defined $binomials{$key};
	$binomials{$key} = _binomial($n, $k);
	$binomials{$key};
}

sub fillings {
	my ($ones, $zeros, $pawns, $par) = @_;
	return 0 if $pawns < 0;
	my $total = 0;
	my $on_ones = $par;
	my $on_zeros = $pawns - $par;
	while ($on_zeros >= 0) {
		$total += binomial($ones, $on_ones) * binomial($zeros, $on_zeros);
		$on_ones += 2;
		$on_zeros -= 2;
	}
	$total;
}

sub calculate {
	my ($n, $m, $k, $par) = @_;
	my $zeros = $n * $m / 2;
	my $ones = $n * $m / 2;
	if (($n * $m) % 2) {
		$zeros = ($n * $m + 1) / 2;
		$ones = ($n * $m - 1) / 2;
	}
	my @moves;
	for my $i (0 .. $n - 1) {
		for my $j (0 .. $m - 1) {
			push @moves, [[$i, $j], [$i - 1, $j]] if $i > 0;
			push @moves, [[$i, $j], [$i, $j - 1]] if $j > 0;
			push @moves, [[$i, $j], [$i + 1, $j]] if $i < $n - 1;
			push @moves, [[$i, $j], [$i, $j + 1]] if $j < $m - 1;
		}
	}
	my $total = 0;
	for my $move (@moves) {
		my ($p1, $p2) = @$move;
		my ($x1, $y1, $x2, $y2) = (@$p1, @$p2);
		$total += fillings($ones - 1, $zeros - 1, $k - 1, ($par + $x1 + $y1) % 2);
	}
	$total;
}
*/

int64_t totals[1024] = {
	0LL, 0LL, 0LL, 0LL, 0LL, 0LL, 0LL, 0LL, 0LL, 0LL, 0LL, 0LL, 0LL, 0LL, 0LL, 0LL, 
	1LL, 1LL, 0LL, 0LL, 0LL, 0LL, 0LL, 0LL, 0LL, 0LL, 0LL, 0LL, 0LL, 0LL, 0LL, 0LL, 
	2LL, 2LL, 2LL, 2LL, 0LL, 0LL, 0LL, 0LL, 0LL, 0LL, 0LL, 0LL, 0LL, 0LL, 0LL, 0LL, 
	3LL, 3LL, 6LL, 6LL, 3LL, 3LL, 0LL, 0LL, 0LL, 0LL, 0LL, 0LL, 0LL, 0LL, 0LL, 0LL, 
	4LL, 4LL, 12LL, 12LL, 12LL, 12LL, 4LL, 4LL, 0LL, 0LL, 0LL, 0LL, 0LL, 0LL, 0LL, 0LL, 
	5LL, 5LL, 20LL, 20LL, 30LL, 30LL, 20LL, 20LL, 5LL, 5LL, 0LL, 0LL, 0LL, 0LL, 0LL, 0LL, 
	6LL, 6LL, 30LL, 30LL, 60LL, 60LL, 60LL, 60LL, 30LL, 30LL, 6LL, 6LL, 0LL, 0LL, 0LL, 0LL, 
	7LL, 7LL, 42LL, 42LL, 105LL, 105LL, 140LL, 140LL, 105LL, 105LL, 42LL, 42LL, 7LL, 7LL, 0LL, 0LL, 
	1LL, 1LL, 0LL, 0LL, 0LL, 0LL, 0LL, 0LL, 0LL, 0LL, 0LL, 0LL, 0LL, 0LL, 0LL, 0LL, 
	4LL, 4LL, 8LL, 8LL, 4LL, 4LL, 0LL, 0LL, 0LL, 0LL, 0LL, 0LL, 0LL, 0LL, 0LL, 0LL, 
	7LL, 7LL, 28LL, 28LL, 42LL, 42LL, 28LL, 28LL, 7LL, 7LL, 0LL, 0LL, 0LL, 0LL, 0LL, 0LL, 
	10LL, 10LL, 60LL, 60LL, 150LL, 150LL, 200LL, 200LL, 150LL, 150LL, 60LL, 60LL, 10LL, 10LL, 0LL, 0LL, 
	13LL, 13LL, 104LL, 104LL, 364LL, 364LL, 728LL, 728LL, 910LL, 910LL, 728LL, 728LL, 364LL, 364LL, 104LL, 104LL, 
	16LL, 16LL, 160LL, 160LL, 720LL, 720LL, 1920LL, 1920LL, 3360LL, 3360LL, 4032LL, 4032LL, 3360LL, 3360LL, 1920LL, 1920LL, 
	19LL, 19LL, 228LL, 228LL, 1254LL, 1254LL, 4180LL, 4180LL, 9405LL, 9405LL, 15048LL, 15048LL, 17556LL, 17556LL, 15048LL, 15048LL, 
	22LL, 22LL, 308LL, 308LL, 2002LL, 2002LL, 8008LL, 8008LL, 22022LL, 22022LL, 44044LL, 44044LL, 66066LL, 66066LL, 75504LL, 75504LL, 
	2LL, 2LL, 2LL, 2LL, 0LL, 0LL, 0LL, 0LL, 0LL, 0LL, 0LL, 0LL, 0LL, 0LL, 0LL, 0LL, 
	7LL, 7LL, 28LL, 28LL, 42LL, 42LL, 28LL, 28LL, 7LL, 7LL, 0LL, 0LL, 0LL, 0LL, 0LL, 0LL, 
	12LL, 12LL, 84LL, 84LL, 252LL, 252LL, 420LL, 420LL, 420LL, 420LL, 252LL, 252LL, 84LL, 84LL, 12LL, 12LL, 
	17LL, 17LL, 170LL, 170LL, 765LL, 765LL, 2040LL, 2040LL, 3570LL, 3570LL, 4284LL, 4284LL, 3570LL, 3570LL, 2040LL, 2040LL, 
	22LL, 22LL, 286LL, 286LL, 1716LL, 1716LL, 6292LL, 6292LL, 15730LL, 15730LL, 28314LL, 28314LL, 37752LL, 37752LL, 37752LL, 37752LL, 
	27LL, 27LL, 432LL, 432LL, 3240LL, 3240LL, 15120LL, 15120LL, 49140LL, 49140LL, 117936LL, 117936LL, 216216LL, 216216LL, 308880LL, 308880LL, 
	32LL, 32LL, 608LL, 608LL, 5472LL, 5472LL, 31008LL, 31008LL, 124032LL, 124032LL, 372096LL, 372096LL, 868224LL, 868224LL, 1612416LL, 1612416LL, 
	37LL, 37LL, 814LL, 814LL, 8547LL, 8547LL, 56980LL, 56980LL, 270655LL, 270655LL, 974358LL, 974358LL, 2760681LL, 2760681LL, 6310128LL, 6310128LL, 
	3LL, 3LL, 6LL, 6LL, 3LL, 3LL, 0LL, 0LL, 0LL, 0LL, 0LL, 0LL, 0LL, 0LL, 0LL, 0LL, 
	10LL, 10LL, 60LL, 60LL, 150LL, 150LL, 200LL, 200LL, 150LL, 150LL, 60LL, 60LL, 10LL, 10LL, 0LL, 0LL, 
	17LL, 17LL, 170LL, 170LL, 765LL, 765LL, 2040LL, 2040LL, 3570LL, 3570LL, 4284LL, 4284LL, 3570LL, 3570LL, 2040LL, 2040LL, 
	24LL, 24LL, 336LL, 336LL, 2184LL, 2184LL, 8736LL, 8736LL, 24024LL, 24024LL, 48048LL, 48048LL, 72072LL, 72072LL, 82368LL, 82368LL, 
	31LL, 31LL, 558LL, 558LL, 4743LL, 4743LL, 25296LL, 25296LL, 94860LL, 94860LL, 265608LL, 265608LL, 575484LL, 575484LL, 986544LL, 986544LL, 
	38LL, 38LL, 836LL, 836LL, 8778LL, 8778LL, 58520LL, 58520LL, 277970LL, 277970LL, 1000692LL, 1000692LL, 2835294LL, 2835294LL, 6480672LL, 6480672LL, 
	45LL, 45LL, 1170LL, 1170LL, 14625LL, 14625LL, 117000LL, 117000LL, 672750LL, 672750LL, 2960100LL, 2960100LL, 10360350LL, 10360350LL, 29601000LL, 29601000LL, 
	52LL, 52LL, 1560LL, 1560LL, 22620LL, 22620LL, 211120LL, 211120LL, 1425060LL, 1425060LL, 7410312LL, 7410312LL, 30876300LL, 30876300LL, 105861600LL, 105861600LL, 
	4LL, 4LL, 12LL, 12LL, 12LL, 12LL, 4LL, 4LL, 0LL, 0LL, 0LL, 0LL, 0LL, 0LL, 0LL, 0LL, 
	13LL, 13LL, 104LL, 104LL, 364LL, 364LL, 728LL, 728LL, 910LL, 910LL, 728LL, 728LL, 364LL, 364LL, 104LL, 104LL, 
	22LL, 22LL, 286LL, 286LL, 1716LL, 1716LL, 6292LL, 6292LL, 15730LL, 15730LL, 28314LL, 28314LL, 37752LL, 37752LL, 37752LL, 37752LL, 
	31LL, 31LL, 558LL, 558LL, 4743LL, 4743LL, 25296LL, 25296LL, 94860LL, 94860LL, 265608LL, 265608LL, 575484LL, 575484LL, 986544LL, 986544LL, 
	40LL, 40LL, 920LL, 920LL, 10120LL, 10120LL, 70840LL, 70840LL, 354200LL, 354200LL, 1345960LL, 1345960LL, 4037880LL, 4037880LL, 9806280LL, 9806280LL, 
	49LL, 49LL, 1372LL, 1372LL, 18522LL, 18522LL, 160524LL, 160524LL, 1003275LL, 1003275LL, 4815720LL, 4815720LL, 18460260LL, 18460260LL, 58017960LL, 58017960LL, 
	58LL, 58LL, 1914LL, 1914LL, 30624LL, 30624LL, 316448LL, 316448LL, 2373360LL, 2373360LL, 13765488LL, 13765488LL, 64238944LL, 64238944LL, 247778784LL, 247778784LL, 
	67LL, 67LL, 2546LL, 2546LL, 47101LL, 47101LL, 565212LL, 565212LL, 4945605LL, 4945605LL, 33630114LL, 33630114LL, 184965627LL, 184965627LL, 845557152LL, 845557152LL, 
	5LL, 5LL, 20LL, 20LL, 30LL, 30LL, 20LL, 20LL, 5LL, 5LL, 0LL, 0LL, 0LL, 0LL, 0LL, 0LL, 
	16LL, 16LL, 160LL, 160LL, 720LL, 720LL, 1920LL, 1920LL, 3360LL, 3360LL, 4032LL, 4032LL, 3360LL, 3360LL, 1920LL, 1920LL, 
	27LL, 27LL, 432LL, 432LL, 3240LL, 3240LL, 15120LL, 15120LL, 49140LL, 49140LL, 117936LL, 117936LL, 216216LL, 216216LL, 308880LL, 308880LL, 
	38LL, 38LL, 836LL, 836LL, 8778LL, 8778LL, 58520LL, 58520LL, 277970LL, 277970LL, 1000692LL, 1000692LL, 2835294LL, 2835294LL, 6480672LL, 6480672LL, 
	49LL, 49LL, 1372LL, 1372LL, 18522LL, 18522LL, 160524LL, 160524LL, 1003275LL, 1003275LL, 4815720LL, 4815720LL, 18460260LL, 18460260LL, 58017960LL, 58017960LL, 
	60LL, 60LL, 2040LL, 2040LL, 33660LL, 33660LL, 359040LL, 359040LL, 2782560LL, 2782560LL, 16695360LL, 16695360LL, 80694240LL, 80694240LL, 322776960LL, 322776960LL, 
	71LL, 71LL, 2840LL, 2840LL, 55380LL, 55380LL, 701480LL, 701480LL, 6488690LL, 6488690LL, 46718568LL, 46718568LL, 272524980LL, 272524980LL, 1323692760LL, 1323692760LL, 
	82LL, 82LL, 3772LL, 3772LL, 84870LL, 84870LL, 1244760LL, 1244760LL, 13381170LL, 13381170LL, 112401828LL, 112401828LL, 768079158LL, 768079158LL, 4389023760LL, 4389023760LL, 
	6LL, 6LL, 30LL, 30LL, 60LL, 60LL, 60LL, 60LL, 30LL, 30LL, 6LL, 6LL, 0LL, 0LL, 0LL, 0LL, 
	19LL, 19LL, 228LL, 228LL, 1254LL, 1254LL, 4180LL, 4180LL, 9405LL, 9405LL, 15048LL, 15048LL, 17556LL, 17556LL, 15048LL, 15048LL, 
	32LL, 32LL, 608LL, 608LL, 5472LL, 5472LL, 31008LL, 31008LL, 124032LL, 124032LL, 372096LL, 372096LL, 868224LL, 868224LL, 1612416LL, 1612416LL, 
	45LL, 45LL, 1170LL, 1170LL, 14625LL, 14625LL, 117000LL, 117000LL, 672750LL, 672750LL, 2960100LL, 2960100LL, 10360350LL, 10360350LL, 29601000LL, 29601000LL, 
	58LL, 58LL, 1914LL, 1914LL, 30624LL, 30624LL, 316448LL, 316448LL, 2373360LL, 2373360LL, 13765488LL, 13765488LL, 64238944LL, 64238944LL, 247778784LL, 247778784LL, 
	71LL, 71LL, 2840LL, 2840LL, 55380LL, 55380LL, 701480LL, 701480LL, 6488690LL, 6488690LL, 46718568LL, 46718568LL, 272524980LL, 272524980LL, 1323692760LL, 1323692760LL, 
	84LL, 84LL, 3948LL, 3948LL, 90804LL, 90804LL, 1362060LL, 1362060LL, 14982660LL, 14982660LL, 128850876LL, 128850876LL, 901956132LL, 901956132LL, 5282885916LL, 5282885916LL, 
	97LL, 97LL, 5238LL, 5238LL, 138807LL, 138807LL, 2405988LL, 2405988LL, 30676347LL, 30676347LL, 306763470LL, 306763470LL, 2505235005LL, 2505235005LL, 17178754320LL, 17178754320LL, 
	7LL, 7LL, 42LL, 42LL, 105LL, 105LL, 140LL, 140LL, 105LL, 105LL, 42LL, 42LL, 7LL, 7LL, 0LL, 0LL, 
	22LL, 22LL, 308LL, 308LL, 2002LL, 2002LL, 8008LL, 8008LL, 22022LL, 22022LL, 44044LL, 44044LL, 66066LL, 66066LL, 75504LL, 75504LL, 
	37LL, 37LL, 814LL, 814LL, 8547LL, 8547LL, 56980LL, 56980LL, 270655LL, 270655LL, 974358LL, 974358LL, 2760681LL, 2760681LL, 6310128LL, 6310128LL, 
	52LL, 52LL, 1560LL, 1560LL, 22620LL, 22620LL, 211120LL, 211120LL, 1425060LL, 1425060LL, 7410312LL, 7410312LL, 30876300LL, 30876300LL, 105861600LL, 105861600LL, 
	67LL, 67LL, 2546LL, 2546LL, 47101LL, 47101LL, 565212LL, 565212LL, 4945605LL, 4945605LL, 33630114LL, 33630114LL, 184965627LL, 184965627LL, 845557152LL, 845557152LL, 
	82LL, 82LL, 3772LL, 3772LL, 84870LL, 84870LL, 1244760LL, 1244760LL, 13381170LL, 13381170LL, 112401828LL, 112401828LL, 768079158LL, 768079158LL, 4389023760LL, 4389023760LL, 
	97LL, 97LL, 5238LL, 5238LL, 138807LL, 138807LL, 2405988LL, 2405988LL, 30676347LL, 30676347LL, 306763470LL, 306763470LL, 2505235005LL, 2505235005LL, 17178754320LL, 17178754320LL, 
	112LL, 112LL, 6944LL, 6944LL, 211792LL, 211792LL, 4235840LL, 4235840LL, 62478640LL, 62478640LL, 724752224LL, 724752224LL, 6885146128LL, 6885146128LL, 55081169024LL, 55081169024LL, 
};

inline board_t read_board() {
	board_t res(n, vector<bool>(m, false));
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			char c;
			scanf("%c", &c);
			if (c == 'O') {
				res[i][j] = true;
			}
		}
		scanf("\n");
	}
	return res;
}

inline int parity(board_t& board) {
	int ret = 0;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			if (board[i][j]) {
				ret += i + j;
			}
		}
	}
	return ret % 2;
}

int main () {
	scanf("%d %d\n", &n, &m);
	int zeros = n * m / 2;
	int ones = n * m / 2;
	if ((n * m) % 2) {
		zeros = (n * m + 1) / 2;
		ones = (n * m + 1) / 2;
	}
	board_t init = read_board();
	int pty = parity(init);
	scanf("\n");
	board_t board = read_board();
	if (pty != parity(board)) {
		printf("0\n");
		return 0;
	}
	int pts = 0;
	int mvs = 0;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			if (board[i][j]) {
				if ((i > 0) && !board[i - 1][j]) {
					++mvs;
				}
				if ((i < n - 1) && !board[i + 1][j]) {
					++mvs;
				}
				if ((j > 0) && !board[i][j - 1]) {
					++mvs;
				}
				if ((j < m - 1) && !board[i][j + 1]) {
					++mvs;
				}
				++pts;
			}
		}
	}
	int64_t total = totals[2 * (8 * (8 * (n - 1) + m - 1) + pts - 1) + pty];
	printf("%.15f", (double)mvs / total);
	return 0;
}