Problem: You have a large rectangular board which is divided into n × 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 ≤ n, m ≤ 3 ⋅ 10^5; nm ≤ 3 ⋅ 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

Solution (in PYTHON3):

Solution:
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)