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

Solution:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.IOException;
import java.io.UncheckedIOException;
import java.io.Closeable;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.InputStream;

/**
 * @author khokharnikunj8
 */
public class Main {
    public static void main(String[] args) throws Exception {
        Thread thread = new Thread(null, new TaskAdapter(), "khokharnikunj8", 1 << 29);
        thread.start();
        thread.join();
    }

    static class TaskAdapter implements Runnable {
        @Override
        public void run() {
            InputStream inputStream = System.in;
            OutputStream outputStream = System.out;
            FastInput in = new FastInput(inputStream);
            FastOutput out = new FastOutput(outputStream);
            EColoringsAndDominoes solver = new EColoringsAndDominoes();
            solver.solve(1, in, out);
            out.close();
        }
    }

    static class EColoringsAndDominoes {
        Modular md = new Modular(998244353);
        int[] temp;
        boolean[][] visited;
        int[][] size;
        int n;
        int m;
        char[][] ar;
        Power pw = new Power(md);

        public void solve(int testNumber, FastInput in, FastOutput out) {
            n = in.readInt();
            m = in.readInt();
            ar = new char[n][];
            for (int i = 0; i < n; i++) ar[i] = in.readString().toCharArray();
            temp = new int[2 * (n * m) + 5];
            temp[2] = 1;
            temp[3] = 3;
            for (int i = 4; i <= 2 * n * m + 3; i++) {
                temp[i] = md.subtract(md.mul(3, temp[i - 1]), md.mul(4, temp[i - 3]));
            }
            size = new int[n][m];
            visited = new boolean[n][m];
            int total = 0;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (ar[i][j] == 'o') {
//                    list = new ArrayList<>();
//                    dfs(i, j);
//                    for (int[] pair : list) {
//                        size[pair[0]][pair[1]] = list.size();
//                    }
//                    total += list.size();
                        total++;
                    }
                }
            }
            int ans = 0;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (ar[i][j] == 'o' && (i == 0 || ar[i - 1][j] != 'o')) {
                        int idx = i;
                        while (idx < n && ar[idx][j] == 'o') {
                            idx++;
                        }
                        int count = idx - i;
                        ans = md.add(ans, md.mul(pw.pow(2, total - count), temp[count]));
                    }
                }
            }
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (ar[i][j] == 'o' && (j == 0 || ar[i][j - 1] != 'o')) {
                        int idx = j;
                        while (idx < m && ar[i][idx] == 'o') {
                            idx++;
                        }
                        int count = idx - j;
                        ans = md.add(ans, md.mul(pw.pow(2, total - count), temp[count]));
                    }
                }
            }
            out.println(ans);
        }

    }

    static class Modular {
        private final int mod;

        public Modular(int mod) {
            this.mod = mod;
        }

        public Modular(long mod) {
            this((int) mod);
            if (this.mod != mod) throw new IllegalArgumentException();
        }

        public Modular(double mod) {
            this((int) mod);
            if (this.mod != mod) throw new IllegalArgumentException();
        }

        public int valueOf(int x) {
            x %= mod;
            if (x < 0) x += mod;
            return x;
        }

        public int valueOf(long x) {
            x %= mod;
            if (x < 0) x += mod;
            return (int) x;
        }

        public int mul(int x, int y) {
            return valueOf((long) x * y);
        }

        public int add(int x, int y) {
            return valueOf(x + y);
        }

        public int subtract(int x, int y) {
            return valueOf(x - y);
        }

        public String toString() {
            return "Mod : " + mod;
        }

    }

    static class FastOutput implements AutoCloseable, Closeable, Appendable {
        private final Writer os;
        private final StringBuilder cache = new StringBuilder(5 << 20);

        public FastOutput(Writer os) {
            this.os = os;
        }

        public FastOutput(OutputStream os) {
            this(new OutputStreamWriter(os));
        }

        public FastOutput append(CharSequence csq) {
            cache.append(csq);
            return this;
        }

        public FastOutput append(CharSequence csq, int start, int end) {
            cache.append(csq, start, end);
            return this;
        }

        public FastOutput append(char c) {
            cache.append(c);
            return this;
        }

        public FastOutput append(int c) {
            cache.append(c);
            return this;
        }

        public FastOutput println(int c) {
            return append(c).println();
        }

        public FastOutput println() {
            cache.append(System.lineSeparator());
            return this;
        }

        public FastOutput flush() {
            try {
                os.append(cache);
                os.flush();
                cache.setLength(0);
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
            return this;
        }

        public void close() {
            flush();
            try {
                os.close();
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
        }

        public String toString() {
            return cache.toString();
        }

    }

    static class Power {
        private final Modular modular;

        public Power(Modular modular) {
            this.modular = modular;
        }

        public int pow(int x, int y) {
            long r = modular.valueOf(1);
            while (y > 0) {
                if ((y & 1) == 1) r = modular.valueOf(r * x);
                x = modular.mul(x, x);
                y >>= 1;
            }
            return modular.valueOf(r);
        }

    }

    static class FastInput {
        private final InputStream is;
        private final StringBuilder defaultStringBuf = new StringBuilder(1 << 13);
        private final byte[] buf = new byte[1 << 13];
        private int bufLen;
        private int bufOffset;
        private int next;

        public FastInput(InputStream is) {
            this.is = is;
        }

        private int read() {
            while (bufLen == bufOffset) {
                bufOffset = 0;
                try {
                    bufLen = is.read(buf);
                } catch (IOException e) {
                    bufLen = -1;
                }
                if (bufLen == -1) {
                    return -1;
                }
            }
            return buf[bufOffset++];
        }

        public void skipBlank() {
            while (next >= 0 && next <= 32) {
                next = read();
            }
        }

        public int readInt() {
            int sign = 1;

            skipBlank();
            if (next == '+' || next == '-') {
                sign = next == '+' ? 1 : -1;
                next = read();
            }

            int val = 0;
            if (sign == 1) {
                while (next >= '0' && next <= '9') {
                    val = val * 10 + next - '0';
                    next = read();
                }
            } else {
                while (next >= '0' && next <= '9') {
                    val = val * 10 - next + '0';
                    next = read();
                }
            }

            return val;
        }

        public String readString(StringBuilder builder) {
            skipBlank();

            while (next > 32) {
                builder.append((char) next);
                next = read();
            }

            return builder.toString();
        }

        public String readString() {
            defaultStringBuf.setLength(0);
            return readString(defaultStringBuf);
        }

    }
}