You have a large rectangular board which is divided into $n \times m$ cells (the board has $n$ rows and $m$ columns). Each cell is either white or black.

You paint each white cell either red or blue. Obviously, the number of different ways to paint them is $2^w$, where $w$ is the number of white cells.

After painting the white cells of the board, you want to place the maximum number of dominoes on it, according to the following rules:

each domino covers two adjacent cells;

each cell is covered by at most one domino;

if a domino is placed horizontally (it covers two adjacent cells in one of the rows), it should cover only red cells;

if a domino is placed vertically (it covers two adjacent cells in one of the columns), it should cover only blue cells.

Let the value of the board be the maximum number of dominoes you can place. Calculate the sum of values of the board over all $2^w$ possible ways to paint it. Since it can be huge, print it modulo $998\,244\,353$.


-----Input-----

The first line contains two integers $n$ and $m$ ($1 \le n, m \le 3 \cdot 10^5$; $nm \le 3 \cdot 10^5$) — the number of rows and columns, respectively.

Then $n$ lines follow, each line contains a string of $m$ characters. The $j$-th character in the $i$-th string is * if the $j$-th cell in the $i$-th row is black; otherwise, that character is o.


-----Output-----

Print one integer — the sum of values of the board over all $2^w$ possible ways to paint it, taken modulo $998\,244\,353$.


-----Examples-----

Input
3 4
**oo
oo*o
**oo
Output
144
Input
3 4
**oo
oo**
**oo
Output
48
Input
2 2
oo
o*
Output
4
Input
1 4
oooo
Output
9


-----Note-----

None

Difficulty: HARD
Tags: Dynamic programming

Combinatorics

Mathematics

Greedy algorithms
Skill types: Dynamic programming

Greedy algorithms

Starter code:

Solutions:
MOD = 998244353

def power(a, b):
	res = 1
	while b > 0:
		if b % 2 == 1:
			res = res * a % MOD
		a = a * a % MOD
		b //= 2
	return res

def inverse(n):
	return power(n, MOD - 2)
(h, w) = map(int, input().split())
grid = [input() for _ in range(h)]
prob = [0, 0]
for c in range(2, max(h, w) + 1):
	prob.append(prob[-1] + (-1) ** c * inverse(power(2, c)))
	prob[-1] %= MOD
res = 0
for r in range(h):
	cnt = 0
	for c in range(w):
		if grid[r][c] == 'o':
			cnt += 1
		else:
			cnt = 0
		res += prob[cnt]
		res %= MOD
for c in range(w):
	cnt = 0
	for r in range(h):
		if grid[r][c] == 'o':
			cnt += 1
		else:
			cnt = 0
		res += prob[cnt]
		res %= MOD
for r in range(h):
	for c in range(w):
		if grid[r][c] == 'o':
			res *= 2
			res %= MOD
print(res)


import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
M = 998244353
(m, n) = map(int, input().split())
if m == 1 and n == 1:
	print(0)
	exit()
dp = [0] * max(m, n)
dp[1] = 1
for i in range(2, len(dp)):
	dp[i] = dp[i - 1] + 2 * dp[i - 2] + pow(2, i - 1, M)
	dp[i] = dp[i] % M
tot = 0
matrix = []
for i in range(m):
	s = input()
	matrix.append(s)
	for j in range(n):
		if matrix[i][j] == ord('o'):
			tot += 1
verb = [[] for i in range(m)]
for i in range(m):
	temp = 0
	for j in range(n):
		if matrix[i][j] == ord('o'):
			temp += 1
		else:
			verb[i].append(temp)
			temp = 0
	verb[i].append(temp)
horb = [[] for j in range(n)]
for j in range(n):
	temp = 0
	for i in range(m):
		if matrix[i][j] == ord('o'):
			temp += 1
		else:
			horb[j].append(temp)
			temp = 0
	horb[j].append(temp)
ans = 0
for i in range(m):
	for ele in verb[i]:
		if ele < 2:
			continue
		ans += dp[ele - 1] * pow(2, tot - ele, M)
		ans = ans % M
for j in range(n):
	for ele in horb[j]:
		if ele < 2:
			continue
		ans += dp[ele - 1] * pow(2, tot - ele, M)
		ans = ans % M
print(ans)


MOD = 998244353
(N, M) = map(int, input().split())
S = [input() for _ in range(N)]
L = max(N, M)
imos = [0] * (L + 2)
for i in range(N):
	cnt = 0
	for j in range(M):
		if S[i][j] == '*':
			cnt = 0
		else:
			cnt += 1
			imos[1] += 1
			imos[cnt + 1] -= 1
for j in range(M):
	cnt = 0
	for i in range(N):
		if S[i][j] == '*':
			cnt = 0
		else:
			cnt += 1
			imos[1] += 1
			imos[cnt + 1] -= 1
ans = 0
for i in range(2, min(L, imos[1] // 2) + 1):
	imos[i] += imos[i - 1]
	ans += imos[i] * pow(2, imos[1] // 2 - i, MOD) * (-1) ** (i % 2) % MOD
	ans %= MOD
print(ans)


(n, m) = map(int, input().split())
S = [input() for i in range(n)]
mod = 998244353
ans = 0
count = 0
for i in range(n):
	for j in range(m):
		if S[i][j] == 'o':
			count += 1
pow2 = 1
N = [0]
for i in range(n):
	N.append((pow2 - N[-1]) % mod)
	pow2 *= 2
	pow2 %= mod
pow2 = 1
M = [0]
for i in range(m):
	M.append((pow2 - M[-1]) % mod)
	pow2 *= 2
	pow2 %= mod
for i in range(n):
	c = 0
	for j in range(m):
		if S[i][j] != 'o':
			c = 0
			continue
		if j != m - 1 and S[i][j + 1] == 'o':
			ans += pow(2, count - c - 2, mod) * M[c + 1]
			ans %= mod
			c += 1
for i in range(m):
	c = 0
	for j in range(n):
		if S[j][i] != 'o':
			c = 0
			continue
		if j != n - 1 and S[j + 1][i] == 'o':
			ans += pow(2, count - c - 2, mod) * N[c + 1]
			ans %= mod
			c += 1
print(ans)


import sys
input = sys.stdin.readline
mod = 998244353
(n, m) = map(int, input().split())
board = [input().strip() for i in range(n)]
ans = 0
tot_c = 0
tot_h = []
tot_v = []
for i in range(n):
	for j in range(m):
		if board[i][j] == 'o':
			tot_c += 1
for i in range(n):
	for j in range(m):
		if board[i][j] == 'o' and (j == 0 or board[i][j - 1] == '*'):
			tot_h.append(1)
		elif board[i][j] == 'o':
			tot_h[-1] += 1
for j in range(m):
	for i in range(n):
		if board[i][j] == 'o' and (i == 0 or board[i - 1][j] == '*'):
			tot_v.append(1)
		elif board[i][j] == 'o':
			tot_v[-1] += 1
paired = [[0] * (max(n, m) + 1) for i in range(2)]
paired[0][1] = paired[1][1] = 1
for i in range(2, max(n, m) + 1):
	paired[0][i] = (2 * paired[1][i - 1] + paired[0][i - 1]) % mod
	paired[1][i] = paired[0][i - 1]
dp = [0] * (max(n, m) + 1)
for i in range(2, max(n, m) + 1):
	dp[i] = (2 * dp[i - 1] + paired[1][i - 1]) % mod
for num_consec in tot_h + tot_v:
	ans = (ans + dp[num_consec] * pow(2, tot_c - num_consec, mod)) % mod
print(ans)


import collections
mod = 998244353
(m, n) = map(int, input().split())
mat = [[0] * n for _ in range(m)]
t = 0
res = 0
com = [0] * (max(m, n) + 2)
com[2] = 1
pow2 = 1
C = collections.defaultdict(int)
for i in range(3, max(m, n) + 1):
	pow2 = (pow2 << 1) % mod
	com[i] = (com[i - 1] + 2 * com[i - 2] + pow2) % mod
for i in range(m):
	s = input()
	count = 0
	for j in range(n):
		if s[j] == 'o':
			mat[i][j] = 1
			t += 1
			count += 1
		else:
			if count >= 2:
				C[count] += 1
			count = 0
	if count >= 2:
		C[count] += 1
for j in range(n):
	count = 0
	for i in range(m):
		if mat[i][j] == 1:
			count += 1
		else:
			if count >= 2:
				C[count] += 1
			count = 0
	if count >= 2:
		C[count] += 1
for count in C.keys():
	res = (res + C[count] * com[count] * pow(2, t - count, mod)) % mod
print(res)


from bisect import *
from collections import *
from math import gcd, ceil, sqrt, floor, inf
from heapq import *
from itertools import *
from operator import add, mul, sub, xor, truediv, floordiv
from functools import *
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())

def A(n):
	return [0] * n

def AI(n, x):
	return [x] * n

def A2(n, m):
	return [[0] * m for i in range(n)]

def G(n):
	return [[] for i in range(n)]

def GP(it):
	return [[ch, len(list(g))] for (ch, g) in groupby(it)]
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc
mod = 10 ** 9 + 7
farr = [1]
ifa = []

def fact(x, mod=0):
	if mod:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr) % mod)
	else:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr))
	return farr[x]

def ifact(x, mod):
	global ifa
	fact(x, mod)
	ifa.append(pow(farr[-1], mod - 2, mod))
	for i in range(x, 0, -1):
		ifa.append(ifa[-1] * i % mod)
	ifa.reverse()

def per(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return fact(i) // fact(i - j)
	return farr[i] * ifa[i - j] % mod

def com(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return per(i, j) // fact(j)
	return per(i, j, mod) * ifa[j] % mod

def catalan(n):
	return com(2 * n, n) // (n + 1)

def isprime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True

def floorsum(a, b, c, n):
	if a == 0:
		return b // c * (n + 1)
	if a >= c or b >= c:
		return floorsum(a % c, b % c, c, n) + b // c * (n + 1) + a // c * n * (n + 1) // 2
	m = (a * n + b) // c
	return n * m - floorsum(c, c - b - 1, a, m - 1)

def inverse(a, m):
	a %= m
	if a <= 1:
		return a
	return (1 - inverse(m, a) * m) // a % m

def lowbit(n):
	return n & -n

class BIT:

	def __init__(self, arr):
		self.arr = arr
		self.n = len(arr) - 1

	def update(self, x, v):
		while x <= self.n:
			self.arr[x] += v
			x += x & -x

	def query(self, x):
		ans = 0
		while x:
			ans += self.arr[x]
			x &= x - 1
		return ans

class ST:

	def __init__(self, arr):
		n = len(arr)
		mx = n.bit_length()
		self.st = [[0] * mx for i in range(n)]
		for i in range(n):
			self.st[i][0] = arr[i]
		for j in range(1, mx):
			for i in range(n - (1 << j) + 1):
				self.st[i][j] = max(self.st[i][j - 1], self.st[i + (1 << j - 1)][j - 1])

	def query(self, l, r):
		if l > r:
			return -inf
		s = (r + 1 - l).bit_length() - 1
		return max(self.st[l][s], self.st[r - (1 << s) + 1][s])

class UFS:

	def __init__(self, n):
		self.parent = [i for i in range(n)]
		self.ranks = [0] * n

	def find(self, x):
		if x != self.parent[x]:
			self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def union(self, u, v):
		(pu, pv) = (self.find(u), self.find(v))
		if pu == pv:
			return False
		if self.ranks[pu] >= self.ranks[pv]:
			self.parent[pv] = pu
			if self.ranks[pv] == self.ranks[pu]:
				self.ranks[pu] += 1
		else:
			self.parent[pu] = pv

def Prime(n):
	c = 0
	prime = []
	flag = [0] * (n + 1)
	for i in range(2, n + 1):
		if not flag[i]:
			prime.append(i)
			c += 1
		for j in range(c):
			if i * prime[j] > n:
				break
			flag[i * prime[j]] = prime[j]
			if i % prime[j] == 0:
				break
	return prime

def dij(s, graph):
	d = {}
	d[s] = 0
	heap = [(0, s)]
	seen = set()
	while heap:
		(dis, u) = heappop(heap)
		if u in seen:
			continue
		seen.add(u)
		for (v, w) in graph[u]:
			if v not in d or d[v] > d[u] + w:
				d[v] = d[u] + w
				heappush(heap, (d[v], v))
	return d

def bell(s, g):
	dis = AI(n, inf)
	dis[s] = 0
	for i in range(n - 1):
		for (u, v, w) in edge:
			if dis[v] > dis[u] + w:
				dis[v] = dis[u] + w
	change = A(n)
	for i in range(n):
		for (u, v, w) in edge:
			if dis[v] > dis[u] + w:
				dis[v] = dis[u] + w
				change[v] = 1
	return dis

def lcm(a, b):
	return a * b // gcd(a, b)

def lis(nums):
	res = []
	for k in nums:
		i = bisect.bisect_left(res, k)
		if i == len(res):
			res.append(k)
		else:
			res[i] = k
	return len(res)

def RP(nums):
	n = len(nums)
	s = set(nums)
	d = {}
	for (i, k) in enumerate(sorted(s), 1):
		d[k] = i
	bi = BIT([0] * (len(s) + 1))
	ans = 0
	for i in range(n - 1, -1, -1):
		ans += bi.query(d[nums[i]] - 1)
		bi.update(d[nums[i]], 1)
	return ans

class DLN:

	def __init__(self, val):
		self.val = val
		self.pre = None
		self.next = None

def nb(i, j, n, m):
	for (ni, nj) in [[i + 1, j], [i - 1, j], [i, j - 1], [i, j + 1]]:
		if 0 <= ni < n and 0 <= nj < m:
			yield (ni, nj)

def topo(n):
	q = deque()
	res = []
	for i in range(1, n + 1):
		if ind[i] == 0:
			q.append(i)
			res.append(i)
	while q:
		u = q.popleft()
		for v in g[u]:
			ind[v] -= 1
			if ind[v] == 0:
				q.append(v)
				res.append(v)
	return res

@bootstrap
def gdfs(r, p):
	for ch in g[r]:
		if ch != p:
			yield gdfs(ch, r)
	yield None

@bootstrap
def dfs(r):
	for v in range(k):
		nb = r * k + v
		if not vis[nb]:
			vis[nb] = 1
			yield dfs(v)
			res.append(v)
	yield None
t = 1
mod = 998244353
for i in range(t):
	(n, m) = RL()
	res = []
	for i in range(n):
		res.append(input())
	l = [[0] * m for i in range(n)]
	u = [[0] * m for i in range(n)]
	cnt = 0
	for i in range(n):
		for j in range(m):
			if res[i][j] == 'o':
				l[i][j] = 1
				u[i][j] = 1
				cnt += 1
				if i:
					u[i][j] += u[i - 1][j]
				if j:
					l[i][j] += l[i][j - 1]
	ans = 0
	v3 = pow(3, mod - 2, mod)
	for i in range(n):
		for j in range(m):
			if u[i][j] > 1:
				x = u[i][j]
				w = pow(2, cnt - x, mod)
				if x & 1:
					ans += w * v3 % mod * (pow(2, x - 1, mod) - 1) % mod
				else:
					ans += w * (1 + v3 % mod * (pow(2, x - 1, mod) - 2)) % mod
				ans %= mod
			if l[i][j] > 1:
				x = l[i][j]
				w = pow(2, cnt - x, mod)
				if x & 1:
					ans += w * v3 % mod * (pow(2, x - 1, mod) - 1) % mod
				else:
					ans += w * (1 + v3 % mod * (pow(2, x - 1, mod) - 2)) % mod
				ans %= mod
	print(ans)


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
s = [input() for i in range(n)]
mod = 998244353
inv = 499122177
(w, res) = (0, 0)
for i in range(n):
	(even, odd) = (0, 1)
	for j in range(m):
		if s[i][j] == '*':
			(even, odd) = (0, 1)
		else:
			res += even * inv
			(even, odd) = (odd * inv, even * inv + inv)
			even %= mod
			odd %= mod
			res %= mod
			w += 1
for j in range(m):
	(even, odd) = (0, 1)
	for i in range(n):
		if s[i][j] == '*':
			(even, odd) = (0, 1)
		else:
			res += even * inv
			(even, odd) = (odd * inv, even * inv + inv)
			even %= mod
			odd %= mod
			res %= mod
for i in range(w):
	res = 2 * res % mod
print(res)


import math
MOD = 998244353
R = lambda type=int: type(input().rstrip())
RV = lambda type=int: list(map(type, input().rstrip().split()))
RVV = lambda N, type=int: [RV(type) for _ in range(N)]

def solve():
	(n, m) = RV()
	A = [R(str) for _ in range(n)]
	s = sum([1 for line in A for c in line if c == 'o'])
	H = [[0] * m for _ in range(n)]
	V = [[0] * m for _ in range(n)]
	r = 0
	for (i, line) in enumerate(A):
		for (j, c) in enumerate(line):
			if c == 'o':
				H[i][j] = (i > 0 and H[i - 1][j] or 0) + 1
				V[i][j] = (j > 0 and V[i][j - 1] or 0) + 1
				if i > 0:
					H[i - 1][j] = 0
				if j > 0:
					V[i][j - 1] = 0
	for line in H + V:
		for c in line:
			if c > 1:
				r += ((3 * c - 2) * pow(2, c - 1, MOD) - pow(-1, c - 1, MOD)) * pow(9, MOD - 2, MOD) * pow(2, s - c, MOD)
	print(r % MOD)
T = 1
for t in range(T):
	solve()


import random
import collections
import string
import math
import copy
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def input():
	return sys.stdin.readline().rstrip('\r\n')
mo = 998244353

def exgcd(a, b):
	if not b:
		return (1, 0)
	(y, x) = exgcd(b, a % b)
	y -= a // b * x
	return (x, y)

def getinv(a, m):
	(x, y) = exgcd(a, m)
	return -1 if x == 1 else x % m

def comb(n, b):
	res = 1
	b = min(b, n - b)
	for i in range(b):
		res = res * (n - i) * getinv(i + 1, mo) % mo
	return res % mo

def quickpower(a, n):
	res = 1
	while n:
		if n & 1:
			res = res * a % mo
		n >>= 1
		a = a * a % mo
	return res

def dis(a, b):
	return abs(a[0] - b[0]) + abs(a[1] - b[1])

def getpref(x):
	if x > 1:
		return x * (x - 1) >> 1
	else:
		return 0

def orafli(upp):
	primes = []
	marked = [False for i in range(upp + 3)]
	prvs = [i for i in range(upp + 3)]
	for i in range(2, upp):
		if not marked[i]:
			primes.append(i)
		for j in primes:
			if i * j >= upp:
				break
			marked[i * j] = True
			prvs[i * j] = j
			if i % j == 0:
				break
	return (primes, prvs)

def lower_ord(c: str) -> int:
	return ord(c) - 97

def upper_ord(c: str) -> int:
	return ord(c) - 65

def read_list():
	return [int(i) for i in input().split()]

def read_int():
	s = input().split()
	if len(s) == 1:
		return int(s[0])
	else:
		return map(int, s)

def ask(s):
	print(f'? {s}', flush=True)

def answer(s):
	print(f'{s}', flush=True)
import traceback, random
pv = 1
su = [0, 0, 1]
bs = 4
for i in range(300001):
	su.append(2 * su[-1])
	su[-1] += pv
	pv = bs - pv
	pv %= mo
	bs <<= 1
	bs %= mo
	su[-1] %= mo
powp = [1]
for i in range(300001):
	powp.append(powp[-1] << 1)
	powp[-1] %= mo

def solve():
	(n, m) = read_int()
	l = []
	bctr = 0
	for i in range(n):
		s = input()
		l.append(s)
		bctr += s.count('o')
	ans = 0
	tp = 1
	for i in l:
		ct = 0
		for j in i:
			if j == 'o':
				ct += 1
			else:
				ans += su[ct] * powp[bctr - ct] % mo
				ans %= mo
				ct = 0
		ans += su[ct] * powp[bctr - ct] % mo
		ans %= mo
	for i in zip(*l):
		ct = 0
		for j in i:
			if j == 'o':
				ct += 1
			else:
				ans += su[ct] * powp[bctr - ct] % mo
				ans %= mo
				ct = 0
		ans += su[ct] * powp[bctr - ct] % mo
		ans %= mo
	print(ans)
t = 1
for ti in range(t):
	solve()


MOD = 998244353
ninv = pow(9, MOD - 2, MOD)

def f(n):
	return ((3 * n + 1) * pow(2, n, MOD) - (1 if n % 2 == 0 else -1)) * ninv
(h, w) = map(int, input().split())
s = ['*' * (w + 2)] + ['*' + input() + '*' for _ in range(h)] + ['*' * (w + 2)]
c = 0
for i in range(h + 2):
	c += s[i].count('o')
ans = 0
for i in range(1, h + 1):
	l = []
	for j in range(w + 1):
		if s[i][j] != s[i][j + 1]:
			l.append(j)
	for j in range(1, len(l), 2):
		ans += f(l[j] - l[j - 1] - 1) * pow(2, c - l[j] + l[j - 1], MOD)
for i in range(1, w + 1):
	l = []
	for j in range(h + 1):
		if s[j][i] != s[j + 1][i]:
			l.append(j)
	for j in range(1, len(l), 2):
		ans += f(l[j] - l[j - 1] - 1) * pow(2, c - l[j] + l[j - 1], MOD)
print(ans % MOD)


(n, m) = map(int, input().split())
s = [input() + '*' for _ in range(n)] + ['*' * (m + 1)]
cnt = sum((i.count('o') for i in s))
MOD = 998244353
ans = 0
inv4 = pow(4, MOD - 2, MOD)
inv2 = pow(2, MOD - 2, MOD)
v = pow(2, cnt, MOD)
for i in range(n + 1):
	cnt = 0
	for j in range(m + 1):
		if s[i][j] == 'o':
			cnt += 1
		else:
			for k in range(cnt - 1):
				ans += inv4 * pow(inv2, k, MOD) * (cnt - 1 - k) * pow(-1, k, MOD)
				ans %= MOD
			cnt = 0
for j in range(m + 1):
	cnt = 0
	for i in range(n + 1):
		if s[i][j] == 'o':
			cnt += 1
		else:
			for k in range(cnt - 1):
				ans += inv4 * pow(inv2, k, MOD) * (cnt - 1 - k) * pow(-1, k, MOD)
				ans %= MOD
			cnt = 0
print(ans * v % MOD)


MOD = 998244353
import sys, os, io
input = sys.stdin.readline
(N, M) = map(int, input().split())
S = [input()[:-1] for _ in range(N)]
L = max(N, M)
imos = [0] * (L + 2)
for i in range(N):
	cnt = 0
	for j in range(M):
		if S[i][j] == '*':
			cnt = 0
		else:
			cnt += 1
			imos[1] += 1
			imos[cnt + 1] -= 1
for j in range(M):
	cnt = 0
	for i in range(N):
		if S[i][j] == '*':
			cnt = 0
		else:
			cnt += 1
			imos[1] += 1
			imos[cnt + 1] -= 1
ans = 0
lis = [1] * (imos[1] // 2 + 1)
for i in range(1, imos[1] // 2 + 1):
	lis[i] = lis[i - 1] * 2 % MOD
for i in range(2, min(L, imos[1] // 2) + 1):
	imos[i] += imos[i - 1]
	ans += imos[i] * lis[imos[1] // 2 - i] * (-1) ** (i % 2) % MOD
	ans %= MOD
print(ans)


from sys import stdin, stdout
mod = 998244353
d = {}

def power(x, y):
	if y < 0:
		return 0
	s = str(x) + '$' + str(y)
	if d.get(s, -1) != -1:
		return d[s]
	f = 1
	y1 = y
	while y:
		if y % 2 == 1:
			f *= x
		x = x * x
		y //= 2
		x %= mod
		f %= mod
	d[s] = f
	return f
ct = 0
(n, m) = [int(i) for i in stdin.readline().split()]
a = [[i for i in stdin.readline()] for j in range(n)]
dp = [[[0, 0] for i in range(m)] for j in range(n)]
c1 = 0
for i in range(n):
	for j in range(m):
		if a[i][j] == 'o':
			dp[i][j] = [1, 1]
			if i > 0:
				dp[i][j][0] += dp[i - 1][j][0]
			if j > 0:
				dp[i][j][1] += dp[i][j - 1][1]
			c1 += 1
for i in range(n):
	for j in range(m):
		if a[i][j] == 'o':
			if i > 0 and a[i - 1][j] == 'o':
				val = dp[i][j][0]
				if val == 2:
					ct += power(2, c1 - 2)
				else:
					no = (val - 1) // 2
					if val % 2 == 0:
						ct += power(2, c1 - val + 1) * (power(4, no) - 1) * power(3, mod - 2) % mod
						ct += power(2, c1 - val)
						ct %= mod
					else:
						ct += power(2, c1 - val) * (power(4, no) - 1) * power(3, mod - 2) % mod
			if j > 0 and a[i][j - 1] == 'o':
				val = dp[i][j][1]
				if val == 2:
					ct += power(2, c1 - 2)
				else:
					no = (val - 1) // 2
					if val % 2 == 0:
						ct += power(2, c1 - val + 1) * (power(4, no) - 1) * power(3, mod - 2) % mod
						ct += power(2, c1 - val)
					else:
						ct += power(2, c1 - val) * (power(4, no) - 1) * power(3, mod - 2) % mod
					ct %= mod
			ct %= mod
stdout.write(str(ct) + '\n')


import sys
input = sys.stdin.readline
MOD = 998244353
(n, m) = map(int, input().rstrip().split())
mapp = [list(input().rstrip()) for _ in range(n)]
dp = [0, 0, 1]
for i in range(3, max(n, m) + 1):
	dp.append((dp[-1] + 2 * dp[-2] + pow(2, i - 2, MOD)) % MOD)
white_lst = []
w = 0
for i in range(n):
	flag = False
	for j in range(m):
		if mapp[i][j] == 'o':
			w += 1
			if not flag:
				flag = True
				white_lst.append(1)
			else:
				white_lst[-1] += 1
		else:
			flag = False
for j in range(m):
	flag = False
	for i in range(n):
		if mapp[i][j] == 'o':
			if not flag:
				flag = True
				white_lst.append(1)
			else:
				white_lst[-1] += 1
		else:
			flag = False
ans = 0
for white_element in white_lst:
	ans = (ans + dp[white_element] * pow(2, w - white_element, MOD)) % MOD
print(ans % MOD)


pow2 = [0 for i in range(300005)]
pow2[0] = 1
for i in range(1, 300005):
	pow2[i] = pow2[i - 1] * 2
	pow2[i] %= 998244353
dp = [0 for i in range(300005)]
dp[2] = 1
for i in range(3, 300005):
	dp[i] = dp[i - 1] + 2 * dp[i - 2] + pow2[i - 2]
	dp[i] %= 998244353
l = input().split()
n = int(l[0])
m = int(l[1])
a = []
for i in range(n):
	s = input()
	a.append(s)
counter = 0
s = a
mod = 998244353
for i in range(n):
	for j in range(m):
		if s[i][j] == 'o':
			counter += 1
ans = 0
for i in range(n):
	start = 0
	end = 0
	done = 0
	for j in range(m):
		if s[i][j] == 'o':
			if done == 0:
				done = 1
				start = j
				end = j
			else:
				end += 1
		elif done == 1:
			length = end - start + 1
			z = dp[length]
			z = z * pow2[counter - length]
			z %= mod
			ans += z
			ans %= mod
			done = 0
	if done:
		length = end - start + 1
		z = dp[length]
		z = z * pow2[counter - length]
		z %= mod
		ans += z
		ans %= mod
		done = 0
for i in range(m):
	start = 0
	end = 0
	done = 0
	for j in range(n):
		if s[j][i] == 'o':
			if done == 0:
				done = 1
				start = j
				end = j
			else:
				end += 1
		elif done == 1:
			length = end - start + 1
			z = dp[length]
			z = z * pow2[counter - length]
			z %= mod
			ans += z
			ans %= mod
			done = 0
	if done:
		length = end - start + 1
		z = dp[length]
		z = z * pow2[counter - length]
		z %= mod
		ans += z
		ans %= mod
		done = 0
print(ans)


mod = 998244353

def qpow(n, k):
	res = 1
	while k:
		if k & 1:
			res = res * n % mod
		n = n * n % mod
		k >>= 1
	return res
(n, m) = map(int, input().split())
mp = []
cnt = 0
for i in range(n):
	mp.append(input())
	for j in mp[-1]:
		if j == 'o':
			cnt += 1
half = qpow(2, mod - 2)
dp = [0, 0]
now = half * half % mod
piece = 0
for i in range(1, cnt + 1):
	piece = (piece + now + mod) % mod
	dp.append((dp[-1] + piece) % mod)
	now = now * half % mod * -1
ans = 0
for i in range(n):
	now = 0
	for j in mp[i]:
		if j == 'o':
			now += 1
		else:
			ans += dp[now]
			now = 0
	ans = (ans + dp[now]) % mod
for i in range(m):
	now = 0
	for j in range(n):
		if mp[j][i] == 'o':
			now += 1
		else:
			ans += dp[now]
			now = 0
	ans = (ans + dp[now]) % mod
ans = ans * qpow(2, cnt) % mod
print(ans)


mod = 998244353
(n, m) = map(int, input().split())
a = [0] * n
dp = [0] * n
dp2 = [0] * n
P = [0] * 300005
for i in range(n):
	dp[i] = [0] * m
	dp2[i] = [0] * m
for i in range(n):
	a[i] = list(input())
cnt = 0
for i in range(n):
	for j in range(m):
		if a[i][j] == 'o':
			cnt += 1
ans = 0
P[2] = pow(2, cnt - 2, mod)
P[3] = pow(2, cnt - 3, mod)
for i in range(3, max(m, n) + 1):
	P[i] = (P[3] + pow(4, -1, mod) * P[i - 2]) % mod
for i in range(n):
	for j in range(m):
		if a[i][j] == 'o':
			dp[i][j] = dp[i][j - 1] + 1
		if dp[i][j] >= 2:
			ans = (ans + P[dp[i][j]]) % mod
for i in range(m):
	for j in range(n):
		if a[j][i] == 'o':
			dp2[j][i] = dp2[j - 1][i] + 1
		if dp2[j][i] >= 2:
			ans = (ans + P[dp2[j][i]]) % mod
print(ans)


import sys
from sys import stdin
mod = 998244353
(H, W) = map(int, stdin.readline().split())
s = [list(stdin.readline()[:-1]) for i in range(H)]
ans = 0
onum = 0
for i in range(H):
	for j in range(W):
		if s[i][j] == 'o':
			onum += 1
for i in range(H):
	to = onum
	dp = [1, 0]
	for j in range(W):
		if s[i][j] == '*':
			dp = [sum(dp) % mod, 0]
		else:
			to -= 1
			ans += pow(2, to, mod) * dp[1]
			ans %= mod
			dp = [(dp[0] + 2 * dp[1]) % mod, dp[0]]
for j in range(W):
	to = onum
	dp = [1, 0]
	for i in range(H):
		if s[i][j] == '*':
			dp = [sum(dp) % mod, 0]
		else:
			to -= 1
			ans += pow(2, to, mod) * dp[1]
			ans %= mod
			dp = [(dp[0] + 2 * dp[1]) % mod, dp[0]]
print(ans % mod)


import io
import os
from collections import Counter, defaultdict, deque
MOD = 998244353
MAX_N = 3 * 10 ** 5 + 10

def modInverse(a, p):
	return pow(a, p - 2, p)
fact = [1]
for i in range(1, MAX_N + 1):
	fact.append(fact[-1] * i % MOD)
invFact = [0] * (MAX_N + 1)
invFact[MAX_N] = modInverse(fact[MAX_N], MOD)
for i in range(MAX_N - 1, -1, -1):
	invFact[i] = invFact[i + 1] * (i + 1) % MOD

def nCr(n, r):
	if n < r:
		return 0
	return fact[n] * invFact[r] * invFact[n - r] % MOD

def f(arr):
	consec = []
	for c in arr:
		if not consec or consec[-1][-1] != c - 1:
			consec.append([c])
		else:
			consec[-1].append(c)
	return consec

def makeConsec(rows):
	for r in rows:
		rows[r].sort()
		consec = f(rows[r])
		consec = list(map(len, consec))
		rows[r] = consec
	return rows

def group(cells):
	rows = defaultdict(list)
	cols = defaultdict(list)
	for (r, c) in cells:
		rows[r].append(c)
		cols[c].append(r)
	return (makeConsec(rows), makeConsec(cols))

def solve1(R, C, grid):
	assert len(grid) == R
	assert len(grid[0]) == C
	whites = [(r, c) for r in range(R) for c in range(C) if grid[r][c] == 0]
	score = 0
	for mask in range(1 << len(whites)):
		reds = []
		blues = []
		for (i, (r, c)) in enumerate(whites):
			if 1 << i & mask:
				reds.append((r, c))
			else:
				blues.append((r, c))
		(redUsable, _) = group(reds)
		(_, blueUsable) = group(blues)
		score += sum((l // 2 for (r, cols) in redUsable.items() for l in cols))
		score += sum((l // 2 for (c, rows) in blueUsable.items() for l in rows))
		score %= MOD
	return score
inv9 = modInverse(9, MOD)

def solve(R, C, grid):
	assert len(grid) == R
	assert len(grid[0]) == C
	whites = [(r, c) for r in range(R) for c in range(C) if grid[r][c] == 0]
	ans = 0
	for grouping in group(whites):
		for k in grouping:
			for l in grouping[k]:
				otherMasks = pow(2, len(whites) - l, MOD)
				if l >= 2:
					l -= 1
					ways = ((3 * l + 1) * pow(2, l, MOD) - pow(-1, l % 2)) * inv9
					ans += otherMasks * ways
					ans %= MOD
	return ans
if False:
	R = 1
	for C in range(1, 10):
		print(C, solve1(R, C, [[0 for i in range(C)]]))
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
TC = 1
for tc in range(1, TC + 1):
	(N, M) = [int(x) for x in input().split()]
	grid = [[int(c == '*') for c in input().decode().rstrip()] for i in range(N)]
	ans = solve(N, M, grid)
	print(ans)


import sys

def putin():
	return map(int, sys.stdin.readline().split())

def f(n):
	return ((3 * n + 1) * 2 ** n - (-1) ** n) // 9

def sol():
	(n, k) = putin()
	A = []
	for i in range(n):
		A.append(list(sys.stdin.readline()))
	O_number = 0
	for i in range(n):
		for j in range(k):
			O_number += A[i][j] == 'o'
	Red = {}
	for i in range(n):
		cur = int(A[i][0] == 'o')
		for j in range(1, k):
			if A[i][j] == 'o':
				if cur > 0:
					cur += 1
				else:
					cur += 1
			elif cur > 0:
				if cur in Red:
					Red[cur] += 1
				else:
					Red[cur] = 1
				cur = 0
		if cur > 0:
			if cur in Red:
				Red[cur] += 1
			else:
				Red[cur] = 1
	Blue = {}
	for i in range(k):
		cur = int(A[0][i] == 'o')
		for j in range(1, n):
			if A[j][i] == 'o':
				if cur > 0:
					cur += 1
				else:
					cur += 1
			elif cur > 0:
				if cur in Blue:
					Blue[cur] += 1
				else:
					Blue[cur] = 1
				cur = 0
		if cur > 0:
			if cur in Blue:
				Blue[cur] += 1
			else:
				Blue[cur] = 1
	answer = 0
	for elem in Red:
		answer += f(elem - 1) * Red[elem] * 2 ** (O_number - elem)
	for elem in Blue:
		answer += f(elem - 1) * Blue[elem] * 2 ** (O_number - elem)
	sys.stdout.write(str(answer % 998244353))
sol()


import sys
from math import gcd
input = sys.stdin.readline

def rec1(a, i, p, z):
	if i == len(a):
		return z
	if a[i] == '*':
		return rec1(a, i + 1, i, z)
	elif p == i - 2:
		return rec1(a, i + 1, i, z + 1) + rec1(a, i + 1, i, z)
	else:
		return rec1(a, i + 1, p, z) + rec1(a, i + 1, i, z)

def rec(a, i, p, pp):
	if i == len(a):
		return 0
	if a[i] == '*':
		return rec(a, i + 1, i, pp)
	elif p == i - 2:
		return rec(a, i + 1, i, pp) + rec(a, i + 1, i, pp) + pp[i + 1]
	else:
		return rec(a, i + 1, p, pp) + rec(a, i + 1, i, pp)

def solve1(a):
	MOD = 998244353
	n = len(a)
	pp = [1] * (n + 1)
	for i in range(n - 1, -1, -1):
		pp[i] = pp[i + 1] * (2 if a[i] == 'o' else 1) % MOD
	dp = [[0, 0] for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		if a[i] == '*':
			dp[i][0] = dp[i + 1][0]
			dp[i][1] = dp[i + 1][0]
		else:
			dp[i][1] = (dp[i + 1][0] + dp[i + 1][0] + pp[i + 1]) % MOD
			dp[i][0] = (dp[i + 1][1] + dp[i + 1][0]) % MOD
	ans = dp[0][0]
	return ans

def solve():
	(n, m) = map(int, input().split())
	a = [input().strip() for i in range(n)]
	total = 0
	for i in range(n):
		total += a[i].count('o')
	MOD = 998244353
	r = 0
	for i in range(n):
		r = (r + solve1(a[i]) * pow(2, total - a[i].count('o'), MOD)) % MOD
	s = [None] * n
	for i in range(m):
		for j in range(n):
			s[j] = a[j][i]
		r = (r + solve1(s) * pow(2, total - s.count('o'), MOD)) % MOD
	print(r)
solve()


import sys
sys.setrecursionlimit(10 ** 5)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.buffer.readline())

def MI():
	return map(int, sys.stdin.buffer.readline().split())

def LI():
	return list(map(int, sys.stdin.buffer.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def BI():
	return sys.stdin.buffer.readline().rstrip()

def SI():
	return sys.stdin.buffer.readline().rstrip().decode()
inf = 10 ** 16
md = 998244353
(h, w) = MI()
ss = [[c == 'o' for c in SI()] for _ in range(h)]
inv4 = pow(4, md - 2, md)
inv8 = pow(8, md - 2, md)
mx = max(h, w) + 5
pp = [0] * mx
pp[0] = inv4
pp[1] = inv8
for i in range(2, mx):
	pp[i] = (pp[i - 2] * inv4 + inv8) % md
ev = [0] * mx
for i in range(2, mx):
	ev[i] = (ev[i - 1] + pp[i - 2]) % md

def RLE(s):
	cw = []
	pc = s[0]
	w = 0
	for c in s:
		if c == pc:
			w += 1
		else:
			cw.append((pc, w))
			w = 1
			pc = c
	cw.append((pc, w))
	return cw

def cal(row):
	global ans
	kv = RLE(row)
	for (k, v) in kv:
		if k:
			ans += ev[v]
		ans %= md
ans = 0
for row in ss:
	cal(row)
for col in zip(*ss):
	cal(col)
s = sum((sum(row) for row in ss))
ans = ans * pow(2, s, md) % md
print(ans)


import os
import sys
from io import BytesIO, IOBase
import threading
from bisect import bisect_right
from math import gcd, log
from collections import Counter
from pprint import pprint
from itertools import permutations
from bisect import bisect_right
MOD = 998244353
inv3 = pow(3, MOD - 2, MOD)

def fixt(t, p):
	ans = 0
	if p == 0:
		return pow(2, t - 2, MOD)
	od = p
	if p % 2 == 0:
		ans += pow(2, t - 2 - p, MOD)
		od -= 1
	low = t - 2 - od
	terms = (od + 1) // 2
	k = inv3 * (pow(4, terms, MOD) - 1)
	k %= MOD
	k2 = pow(2, low, MOD)
	ans += k * k2
	ans %= MOD
	return ans

def main():
	(n, m) = map(int, input().split())
	grid = []
	t = 0
	for i in range(n):
		grid.append([c for c in input()])
		t += grid[-1].count('o')
	ans = 0
	for i in range(n):
		last = 0
		for j in range(m):
			if j < m - 1 and grid[i][j] == grid[i][j + 1] == 'o':
				ans += fixt(t, last)
				ans %= MOD
			if grid[i][j] == 'o':
				last += 1
			else:
				last = 0
	for j in range(m):
		last = 0
		for i in range(n):
			if i < n - 1 and grid[i][j] == grid[i + 1][j] == 'o':
				ans += fixt(t, last)
				ans %= MOD
			if grid[i][j] == 'o':
				last += 1
			else:
				last = 0
	print(ans % MOD)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
for _ in range(1):
	main()


import sys
input = sys.stdin.readline
MOD = 998244353

def solve(N, M, B):
	pow2 = [1] * (3 * 10 ** 5 + 10)
	for i in range(1, len(pow2)):
		pow2[i] = pow2[i - 1] * 2 % MOD
	dp = [0] * (3 * 10 ** 5 + 10)
	for i in range(2, len(dp)):
		dp[i] = 2 * dp[i - 2] + pow2[i - 2] + dp[i - 1]
		dp[i] %= MOD
	w_count = sum((sum(b) for b in B))
	ans = 0
	for n in range(N):
		current = 0
		for m in range(M):
			if B[n][m]:
				current += 1
				continue
			r = w_count - current
			ans += dp[current] * pow2[r] % MOD
			ans %= MOD
			current = 0
	for m in range(M):
		current = 0
		for n in range(N):
			if B[n][m]:
				current += 1
				continue
			r = w_count - current
			ans += dp[current] * pow2[r] % MOD
			ans %= MOD
			current = 0
	return ans

def main():
	(N, M) = map(int, input().split())
	B = [[] for _ in range(N)]
	for i in range(N):
		B[i] = [c == 'o' for c in input()] + [0]
	B.append([0] * (M + 1))
	ans = solve(N + 1, M + 1, B)
	print(ans)
main()


from sys import stdin, stdout
MOD = 998244353
b1 = 0
b2 = 0
b3 = 0

def colorings_and_dominoes(n, m, s_a):
	r = 0
	c = sum((s.count('o') for s in s_a))
	b_a = [1 for _ in range(c + 1)]
	if c >= 2:
		b_a[2] = bpow(c - 2)
	if c >= 3:
		b_a[3] = bpow(c - 3)
	for i in range(4, c + 1, 1):
		if i % 2 == 0:
			b_a[i] = b_a[i - 1] + bpow(c - i)
		else:
			b_a[i] = b_a[i - 2] + bpow(c - i)
		b_a[i] %= MOD
	for i in range(n):
		uc = 0
		for j in range(m):
			if s_a[i][j] == 'o':
				uc += 1
			else:
				uc = 0
			if uc >= 2:
				r += b_a[uc]
				r %= MOD
	for j in range(m):
		uc = 0
		for i in range(n):
			if s_a[i][j] == 'o':
				uc += 1
			else:
				uc = 0
			if uc >= 2:
				r += b_a[uc]
				r %= MOD
	return r

def bpow(c):
	if c == 0:
		return 1
	r = bpow(c // 2)
	r *= r
	r %= MOD
	if c % 2 == 1:
		r *= 2
		r %= MOD
	return r
(n, m) = map(int, stdin.readline().split())
s_a = []
for _ in range(n):
	s_a.append(stdin.readline().strip())
r = colorings_and_dominoes(n, m, s_a)
stdout.write(str(r) + '\n')


from sys import stdin
input = stdin.readline

def A():
	t = int(input())
	for _ in range(t):
		n = int(input())
		r = list(map(int, input().split()))
		s = 0
		for i in r:
			if i == 1 or i == 3:
				s += 1
		print(s)

def B():
	t = int(input())
	for _ in range(t):
		(a, b, c) = map(int, input().split())
		(a1, b1, c1) = (1, 1, 1)
		while len(str(c1)) < c:
			c1 *= 2
			b1 *= 2
			a1 *= 2
		while len(str(b1)) < b:
			b1 *= 3
		while len(str(a1)) < a:
			a1 *= 5
		print(a1, b1)

def C():
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	t = list(map(int, input().split()))
	ans = [0] * q
	c = [n + 2] * 51
	for i in range(n):
		if c[a[i]] == n + 2:
			c[a[i]] = i
	for ind in range(q):
		i = t[ind]
		x = c[i]
		for y in range(len(c)):
			if c[y] < x:
				c[y] += 1
		ans[ind] = x + 1
		c[i] = 0
	print(*ans)

def D():
	(n, k) = map(int, input().split())
	z = [chr(ord('a') + x) for x in range(26)]
	s = []
	for a in range(k):
		s.append(z[a])
		for b in range(a + 1, k):
			s.append(z[a] + z[b])
	s = ''.join(s)
	while len(s) < n:
		s *= 2
	print(s[:n])

def E():
	(n, m) = map(int, input().split())
	g = [0 for i in range(n)]
	s = 0
	for i in range(n):
		g[i] = list(input().rstrip())
		for j in g[i]:
			if j == 'o':
				s += 1
	mod = 998244353
	if s == 0:
		print(0)
		return
	q = [0] * (s + 1)
	q[0] = 0
	q[1] = 0
	for i in range(2, s + 1):
		q[i] = (q[i - 1] + 2 * q[i - 2] + pow(2, i - 2, mod)) % mod
	seqs = [0] * (s + 1)
	seq = 0
	for i in range(n):
		for j in range(m):
			if g[i][j] == 'o':
				seq += 1
			elif seq > 0:
				seqs[seq] += 1
				seq = 0
		if seq > 0:
			seqs[seq] += 1
			seq = 0
	seq = 0
	for j in range(m):
		for i in range(n):
			if g[i][j] == 'o':
				seq += 1
			elif seq > 0:
				seqs[seq] += 1
				seq = 0
		if seq > 0:
			seqs[seq] += 1
			seq = 0
	tot = 0
	for i in range(1, s + 1):
		prod = seqs[i] * q[i] % mod
		prod = prod * pow(2, s - i, mod) % mod
		tot += prod
	print(tot % mod)
E()


import os, sys
from io import BytesIO, IOBase

def main():
	mod = 998244353
	powe = [1]
	for i in range(1, 3 * 10 ** 5 + 1):
		powe.append(powe[-1] * 4 % mod)
	(a, b) = (pow(3, mod - 2, mod), pow(9, mod - 2, mod))
	(dp, su) = ([0, 0], 0)
	for i in range(2, 3 * 10 ** 5 + 1):
		(z, zz, zzz, zzzz) = ((i + 1) // 2, i // 2, (i - 1) // 2, (i - 2) // 2)
		x = (su + zz + (powe[z] * (zzz - z + 1) - zzz) * a + (powe[z] - 4) * b + ((powe[zz] * (zzzz - zz + 1) - zzzz) * a + (powe[zz] - 4) * b) * 2) % mod
		dp.append(x)
		su = (su + x) % mod
	(n, m) = map(int, input().split())
	arr = [input().strip() for _ in range(n)]
	z = sum((arr[i][j] == 'o' for i in range(n) for j in range(m)))
	powe = [1]
	for i in range(1, 3 * 10 ** 5 + 1):
		powe.append(powe[-1] * 2 % mod)
	ans = 0
	for i in range(n):
		c = 0
		for j in range(m):
			if arr[i][j] == '*' and c:
				ans = (ans + dp[c] * powe[z - c]) % mod
				c = 0
			elif arr[i][j] == 'o':
				c += 1
		if c:
			ans = (ans + dp[c] * powe[z - c]) % mod
	for i in range(m):
		c = 0
		for j in range(n):
			if arr[j][i] == '*' and c:
				ans = (ans + dp[c] * powe[z - c]) % mod
				c = 0
			elif arr[j][i] == 'o':
				c += 1
		if c:
			ans = (ans + dp[c] * powe[z - c]) % mod
	print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


class Matrix:
	mod = 998244353

	def set_mod(m):
		Matrix.mod = m

	def __init__(self, L):
		self.row = len(L)
		self.column = len(L[0])
		self._matrix = L
		for i in range(self.row):
			for j in range(self.column):
				self._matrix[i][j] %= Matrix.mod

	def __getitem__(self, item):
		if type(item) == int:
			raise IndexError('you must specific row and column')
		elif len(item) != 2:
			raise IndexError('you must specific row and column')
		(i, j) = item
		return self._matrix[i][j]

	def __setitem__(self, item, val):
		if type(item) == int:
			raise IndexError('you must specific row and column')
		elif len(item) != 2:
			raise IndexError('you must specific row and column')
		(i, j) = item
		self._matrix[i][j] = val

	def __add__(self, other):
		if (self.row, self.column) != (other.row, other.column):
			raise SizeError('sizes of matrixes are different')
		res = [[0 for j in range(self.column)] for i in range(self.row)]
		for i in range(self.row):
			for j in range(self.column):
				res[i][j] = self._matrix[i][j] + other._matrix[i][j]
				res[i][j] %= Matrix.mod
		return Matrix(res)

	def __sub__(self, other):
		if (self.row, self.column) != (other.row, other.column):
			raise SizeError('sizes of matrixes are different')
		res = [[0 for j in range(self.column)] for i in range(self.row)]
		for i in range(self.row):
			for j in range(self.column):
				res[i][j] = self._matrix[i][j] - other._matrix[i][j]
				res[i][j] %= Matrix.mod
		return Matrix(res)

	def __mul__(self, other):
		if type(other) != int:
			if self.column != other.row:
				raise SizeError('sizes of matrixes are different')
			res = [[0 for j in range(other.column)] for i in range(self.row)]
			for i in range(self.row):
				for j in range(other.column):
					temp = 0
					for k in range(self.column):
						temp += self._matrix[i][k] * other._matrix[k][j]
					res[i][j] = temp % Matrix.mod
			return Matrix(res)
		else:
			n = other
			res = [[n * self._matrix[i][j] % Matrix.mod for j in range(self.column)] for i in range(self.row)]
			return Matrix(res)

	def __pow__(self, m):
		if self.column != self.row:
			raise MatrixPowError('the size of row must be the same as that of column')
		n = self.row
		res = Matrix([[int(i == j) for i in range(n)] for j in range(n)])
		while m:
			if m % 2 == 1:
				res = res * self
			self = self * self
			m //= 2
		return res

	def __str__(self):
		res = []
		for i in range(self.row):
			for j in range(self.column):
				res.append(str(self._matrix[i][j]))
				res.append(' ')
			res.append('\n')
		res = res[:len(res) - 1]
		return ''.join(res)

def mul(f, g, mod):
	res = [0 for i in range(len(f) + len(g) - 1)]
	for i in range(len(f)):
		for j in range(len(g)):
			res[i + j] += f[i] * g[j]
			res[i + j] %= mod
	return res
import sys, random, bisect
from collections import deque, defaultdict
from heapq import heapify, heappop, heappush
from itertools import permutations
from math import gcd, log
input = lambda : sys.stdin.readline().rstrip()
mi = lambda : map(int, input().split())
li = lambda : list(mi())
mod = 998244353
pow_2 = [1 for i in range(3 * 10 ** 5 + 1)]
for i in range(1, 3 * 10 ** 5 + 1):
	pow_2[i] = 2 * pow_2[i - 1] % mod

def solve(m):
	mod = 998244353
	dp = [0 for i in range(m + 1)]
	dp[1] = 0
	for i in range(2, m + 1):
		dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 2] + pow(2, i - 2, mod)
		dp[i] %= mod
	return dp[m]
dp = [0 for i in range(3 * 10 ** 5 + 1)]
dp[1] = 0
for i in range(2, 3 * 10 ** 5 + 1):
	dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 2] + pow_2[i - 2]
	dp[i] %= mod
(n, m) = mi()
s = [input() for i in range(n)]
w = 0
for i in range(n):
	w += s[i].count('o')
res = 0
mod = 998244353
for i in range(n):
	val = s[i][0]
	cnt = 1
	for j in range(1, m):
		if val == s[i][j]:
			cnt += 1
		else:
			if val == 'o':
				res += dp[cnt] * pow_2[w - cnt]
				res %= mod
			val = s[i][j]
			cnt = 1
	if val == 'o':
		res += dp[cnt] * pow_2[w - cnt]
		res %= mod
for j in range(m):
	val = s[0][j]
	cnt = 1
	for i in range(1, n):
		if val == s[i][j]:
			cnt += 1
		else:
			if val == 'o':
				res += dp[cnt] * pow_2[w - cnt]
				res %= mod
			val = s[i][j]
			cnt = 1
	if val == 'o':
		res += dp[cnt] * pow_2[w - cnt]
		res %= mod
print(res)


(n, m) = map(int, input().split())
maze = []
for i in range(n):
	maze.append(input())
tot = 0
for i in range(n):
	for j in range(m):
		if maze[i][j] == 'o':
			tot += 1
lis = [0 for i in range(max(n, m) + 1)]
for i in range(n):
	j = 0
	while j < m:
		p = j
		while p < m and maze[i][j] == maze[i][p]:
			p += 1
		leng = p - j
		j = p
		if maze[i][j - 1] == '*':
			continue
		if leng > 1:
			lis[leng] += 1
for j in range(m):
	i = 0
	while i < n:
		p = i
		while p < n and maze[i][j] == maze[p][j]:
			p += 1
		leng = p - i
		i = p
		if maze[i - 1][j] == '*':
			continue
		if leng > 1:
			lis[leng] += 1
pre = [0 for i in range(max(n, m) + 1)]
ans = 0
mod = 998244353
for i in range(2, min(max(n, m), tot) + 1):
	pre[i] = (((i - 1) * pow(2, i - 2, mod) - pre[i - 1]) % mod + mod) % mod
	ans += pre[i] * lis[i] % mod * pow(2, tot - i, mod) % mod
	ans %= mod
print(ans)


import sys

def I():
	return int(sys.stdin.readline().rstrip())

def MI():
	return map(int, sys.stdin.readline().rstrip().split())

def LI():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def LI2():
	return list(map(int, sys.stdin.readline().rstrip()))

def S():
	return sys.stdin.readline().rstrip()

def LS():
	return list(sys.stdin.readline().rstrip().split())

def LS2():
	return list(sys.stdin.readline().rstrip())
(n, m) = MI()
board = [S() for _ in range(n)]
mod = 998244353
power = [1]
for _ in range(n * m + 10):
	power.append(2 * power[-1] % mod)
M = max(n, m)
X = [0] * (M + 1)
A = [0] * (M + 1)
A[1] = 1
for i in range(2, M + 1):
	a = -A[i - 1] + power[i - 1]
	a %= mod
	A[i] = a
for i in range(2, M + 1):
	x = 2 * X[i - 1] + A[i - 1]
	x %= mod
	X[i] = x
red = []
blue = []
white = 0
for i in range(n):
	count = 0
	for j in range(m):
		if board[i][j] == 'o':
			count += 1
			white += 1
		else:
			if count >= 2:
				red.append(count)
			count = 0
	if count >= 2:
		red.append(count)
for j in range(m):
	count = 0
	for i in range(n):
		if board[i][j] == 'o':
			count += 1
		else:
			if count >= 2:
				blue.append(count)
			count = 0
	if count >= 2:
		blue.append(count)
ans = 0
for i in red + blue:
	ans += X[i] * power[white - i]
	ans %= mod
print(ans)


def pot2mod(blancos, memo=[1]):
	if blancos < 0:
		return 0.5
	if blancos < len(memo):
		return memo[blancos]
	global NUMMOD
	for i in range(len(memo), blancos + 1):
		memo.append(memo[i - 1] * 2 % NUMMOD)
	return memo[blancos]
NUMMOD = 998244353 * 8
(n, m) = map(int, input().split())
esblanco = [[False for x in range(m + 1)]]
for y in range(n):
	esblanco.append([False] + [x != '*' for x in input()])
blancos = 0
for renglon in esblanco:
	for x in renglon:
		if x:
			blancos += 1
blancos -= 2
suma = 0
nume = [[0 for x in range(m + 1)] for y in range(n + 1)]
numeren = 0
denoren = 0
for y in range(1, n + 1):
	for x in range(1, m + 1):
		if esblanco[y][x] and esblanco[y][x - 1]:
			denoren += 1
			numeren = (pot2mod(denoren) - numeren) % NUMMOD
			suma += numeren * pot2mod(blancos - denoren) % NUMMOD
		else:
			denoren = 0
			numeren = 0
		nume[y][x] = numeren / pot2mod(denoren)
for x in range(1, m + 1):
	for y in range(1, n + 1):
		if esblanco[y][x] and esblanco[y - 1][x]:
			denoren += 1
			numeren = (pot2mod(denoren) - numeren) % NUMMOD
			suma += numeren * pot2mod(blancos - denoren) % NUMMOD
		else:
			denoren = 0
			numeren = 0
		nume[y][x] = numeren / pot2mod(denoren)
print(int(suma % (NUMMOD / 8)))


p = 998244353
pow = [1]
for i in range(1, 3 * 10 ** 5 + 1):
	pow.append(2 * pow[-1] % p)
dp = [0] * (3 * 10 ** 5 + 1)
dp[2] = 1
for i in range(3, 3 * 10 ** 5 + 1):
	dp[i] = (pow[i - 2] + dp[i - 1] + 2 * dp[i - 2]) % p
(n, m) = map(int, input().split())
b = []
for i in range(n):
	b.append(input())
res = []
cnt = 0
for i in range(n):
	res.append(0)
	for j in range(m):
		if b[i][j] == '*':
			res.append(0)
		else:
			cnt += 1
			res[-1] += 1
for j in range(m):
	res.append(0)
	for i in range(n):
		if b[i][j] == '*':
			res.append(0)
		else:
			res[-1] += 1
ans = 0
for j in res:
	if j == 0:
		pass
	else:
		ans = (ans + dp[j] * pow[cnt - j] % p) % p
print(ans)


(n, m) = map(int, input().split())
g = [input() for _ in range(n)]
mod = 998244353
two = [1, 2, 4, 8]
dp = [0, 0, 1, 3]
ct = 8
for i in range(4, n * m + 1):
	ct *= 2
	ct %= mod
	two.append(ct)
	dp.append((dp[i - 1] + 2 * dp[i - 2] + two[i - 2]) % mod)
white = 0
ans = 0
for i in range(n):
	for j in range(m):
		if g[i][j] == 'o':
			white += 1
for i in range(n):
	mid = 0
	for j in range(m):
		if g[i][j] == 'o':
			mid += 1
		else:
			ans += dp[mid] * two[white - mid]
			ans %= mod
			mid = 0
	ans += dp[mid] * two[white - mid]
	ans %= mod
for j in range(m):
	mid = 0
	for i in range(n):
		if g[i][j] == 'o':
			mid += 1
		else:
			ans += dp[mid] * two[white - mid]
			ans %= mod
			mid = 0
	ans += dp[mid] * two[white - mid]
	ans %= mod
print(ans)


import os, sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
MOD = 998244353
mod_inv2 = (MOD + 1) // 2
(N, M) = list(map(int, input().split()))
grid = [input() for _ in range(N)]
ans = 0
num = 0
for i in range(N):
	e = 0
	o = 1
	for j in range(M):
		if grid[i][j] == 'o':
			ans = (ans + e * mod_inv2) % MOD
			(e, o) = (o * mod_inv2 % MOD, (e + 1) * mod_inv2 % MOD)
			num += 1
		else:
			e = 0
			o = 1
for j in range(M):
	e = 0
	o = 1
	for i in range(N):
		if grid[i][j] == 'o':
			ans = (ans + e * mod_inv2) % MOD
			(e, o) = (o * mod_inv2 % MOD, (e + 1) * mod_inv2 % MOD)
		else:
			e = 0
			o = 1
ans = ans * pow(2, num, MOD) % MOD
print(ans)


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
grid = []
for i in range(n):
	grid.append(input())
ans = 0
MOD = 998244353
count = 0
for i in range(n):
	for j in range(m):
		if grid[i][j] == 'o':
			count += 1
if count < 2:
	print(0)
	exit()
s = pow(2, count - 2, MOD)
inv3 = pow(3, MOD - 2, MOD)
inv4 = pow(4, MOD - 2, MOD)
for i in range(n):
	tmp = 0
	for j in range(m):
		if grid[i][j] == 'o':
			tmp += 1
		else:
			tmp = 0
		if tmp >= 2:
			if tmp == 2:
				ans = (ans + s) % MOD
			elif tmp % 2 == 0:
				n1 = tmp // 2 - 1
				n4 = pow(4, n1, MOD)
				n4inv = pow(n4, MOD - 2, MOD)
				ans = (ans + s - (n4 - 1) * n4inv % MOD * inv3 % MOD * s) % MOD
			else:
				n1 = tmp // 2
				n4 = pow(4, n1, MOD)
				n4inv = pow(n4, MOD - 2, MOD)
				ans = (ans + s - (n4 - 1) * n4inv % MOD * inv3 % MOD * s) % MOD
				ans = (ans - s * n4inv) % MOD
for i in range(m):
	tmp = 0
	for j in range(n):
		if grid[j][i] == 'o':
			tmp += 1
		else:
			tmp = 0
		if tmp >= 2:
			if tmp == 2:
				ans = (ans + s) % MOD
			elif tmp % 2 == 0:
				n1 = tmp // 2 - 1
				n4 = pow(4, n1, MOD)
				n4inv = pow(n4, MOD - 2, MOD)
				ans = (ans + s - (n4 - 1) * n4inv % MOD * inv3 % MOD * s) % MOD
			else:
				n1 = tmp // 2
				n4 = pow(4, n1, MOD)
				n4inv = pow(n4, MOD - 2, MOD)
				ans = (ans + s - (n4 - 1) * n4inv % MOD * inv3 % MOD * s) % MOD
				ans = (ans - s * n4inv) % MOD
print(ans)