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

Solution:
#include<bits/stdc++.h> // 65 79 "Baklol☺, Take it easy"
using namespace std;

// #include<ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds;

using ll = long long int;
using ld = long double;
using ull = unsigned long long int;

#define rep(x, k, n)        for(int x = (k); x <= (n); ++x)
#define rept(x, k, n)       for(int x = (k); x < (n); ++x)
#define repr(x, k, n)       for(int x = (k); x >= (n); --x)
#define pb                  push_back
#define F                   first
#define S                   second
#define siz(x)              ((int)(x).size())
#define o2(x)               ((x) * (x))
#define all(x)              (x).begin(), (x).end()
#define clr(x, k)           memset(x, k, sizeof(x)) // 0, -1
#define printv(v, k, n)     rep(i, k, n) cout << v[i] << " \n"[i==n];
#define print2dv(V,k,n,m)   rep(j, k, n) printv(V[j], k, m);
#define report(x)           cout << ((x) ? "Yes" : "No") << '\n'
#define getunique(x, y)     unique(x, y) - (x); // array should be shorted
#define setbits(x)          __builtin_popcountll(x)
#define int                 long long // "be carefull"

typedef vector<int>         vi;
typedef pair<int, int>      pii;

// typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> pbds;

template <typename Arg1>
void debug_out(const char* name, Arg1&& arg1){
    cerr << name << " = " << arg1  << " ]" << "\n";
}

template <typename Arg1, typename... Args>
void debug_out(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');
    cerr.write(names, comma - names) << " = " << arg1 << ",";
    debug_out(comma+1, args...);
}

#ifdef LOCAL
#define deb(...)            cerr << "[ ", debug_out(#__VA_ARGS__, __VA_ARGS__)
#define debv(v, k, n)       rep(i, k, n) cerr << v[i] << " \n"[i==n];
#define deb2dv(V, k, n, m)  rep(j, k, n) debv(V[j], k, m);
#define line                rep(i, 1, 50) cerr << "-\n"[i==50];
#else
#define deb(...)
#define debv(v, k, n)
#define deb2dv(V, k, n, m)
#define line
#endif

constexpr long long inf = 2e9, ninf = -2e9;
constexpr long double eps = 1e-9;
constexpr long double pi = 3.141592653589793238;
constexpr int mod = 998244353; // 998244353;
constexpr int N = 3e5 + 5, M = 2e5 + 5;

/*/-------------------------------- MODINT --------------------------------/*/
template <int32_t MOD_> struct modnum {
    static constexpr int32_t MOD = MOD_;
    static_assert(MOD_ > 0, "MOD must be positive");

private:
    using ll = long long;

    int32_t v;

    static int32_t minv(int32_t a, int32_t m) {
        a %= m;
        assert(a);
        return a == 1 ? 1 : int32_t(m - ll(minv(m, a)) * ll(m) / a);
    }

public: 
    modnum() : v(0) {}
    modnum(ll v_) : v(int32_t(v_ % MOD)) { if (v < 0) v += MOD; }
    explicit operator int32_t() const { return v; }
    friend std::ostream& operator << (std::ostream& out, const modnum& n) { return out << int32_t(n); }
    friend std::istream& operator >> (std::istream& in, modnum& n) { ll v_; in >> v_; n = modnum(v_); return in; }

    friend bool operator == (const modnum& a, const modnum& b) { return a.v == b.v; }
    friend bool operator != (const modnum& a, const modnum& b) { return a.v != b.v; }

    modnum inv() const {
        modnum res;
        res.v = minv(v, MOD);
        return res;
    }
    friend modnum inv(const modnum& m) { return m.inv(); }
    modnum neg() const {
        modnum res;
        res.v = v ? MOD-v : 0;
        return res;
    }
    friend modnum neg(const modnum& m) { return m.neg(); }
 
    modnum operator- () const {
        return neg();
    }
    modnum operator+ () const {
        return modnum(*this);
    }
 
    modnum& operator ++ () {
        v ++;
        if (v == MOD) v = 0;
        return *this;
    }
    modnum& operator -- () {
        if (v == 0) v = MOD;
        v --;
        return *this;
    }
    modnum& operator += (const modnum& o) {
        v += o.v;
        if (v >= MOD) v -= MOD;
        return *this;
    }
    modnum& operator -= (const modnum& o) {
        v -= o.v;
        if (v < 0) v += MOD;
        return *this;
    }
    modnum& operator *= (const modnum& o) {
        v = int32_t(ll(v) * ll(o.v) % MOD);
        return *this;
    }
    modnum& operator /= (const modnum& o) {
        return *this *= o.inv();
    }

    friend modnum operator ++ (modnum& a, int32_t) { modnum r = a; ++a; return r; }
    friend modnum operator -- (modnum& a, int32_t) { modnum r = a; --a; return r; }
    friend modnum operator + (const modnum& a, const modnum& b) { return modnum(a) += b; }
    friend modnum operator - (const modnum& a, const modnum& b) { return modnum(a) -= b; }
    friend modnum operator * (const modnum& a, const modnum& b) { return modnum(a) *= b; }
    friend modnum operator / (const modnum& a, const modnum& b) { return modnum(a) /= b; }
};
using mint = modnum<mod>;
/*/-------------------------------- MODINT --------------------------------/*/

/*/------------------------------ CODE BEGINS ------------------------------/*/

int n, m;
string g[N];
mint dp[N][2], power_2[N];
bool vis[N][2];

mint solve(int rem, int prev){
    if(rem <= 0) return 0;
    mint &res = dp[rem][prev];
    bool &done = vis[rem][prev];
    if(done) return res;
    done = true;
    if(prev == 1) res = power_2[rem-1] + solve(rem-1, 0) + solve(rem-1, 0);
    else res = solve(rem-1, 1) + solve(rem-1, 0);
    return res;
}

void pre_solve(int mx){
    power_2[0] = 1;
    for(int i = 1; i <= mx; i++){
        power_2[i] = 2 * power_2[i-1];
    }
    solve(mx, 0);
}

void DONT_ASSUME_BLINDLY() {

    cin >> n >> m;
    int cnt_w = 0;
    rept(i, 0, n){
        cin >> g[i];
        g[i].pb('*');
        cnt_w += count(all(g[i]), 'o');
    }
    g[n] = string(m, '*');
    deb(cnt_w);
    assert(n * m < N);
    pre_solve(n * m);
    mint res = 0;
    rept(i, 0, n){
        int cnt = 0;
        rep(j, 0, m){
            if(j == m) assert(g[i][j] == '*');
            if(g[i][j] == 'o') cnt++;
            else{
                assert(cnt <= cnt_w);
                res += dp[cnt][0] * power_2[cnt_w - cnt];
                cnt = 0;
            }
        }
    }
    rept(j, 0, m){
        int cnt = 0;
        rep(i, 0, n){
            if(i == n) assert(g[i][j] == '*');
            if(g[i][j] == 'o') cnt++;
            else{
                assert(cnt <= cnt_w);
                res += dp[cnt][0] * power_2[cnt_w - cnt];
                cnt = 0;
            }
        }
    }
    cout << res << '\n';
}

/*/------------------------------- CODE ENDS -------------------------------/*/

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);

    // cout << setprecision(12) << fixed;
    int tc = 1;
    // cin >> tc;
    for(int i = 1; i <= tc; i++) {
        DONT_ASSUME_BLINDLY();
#ifdef LOCAL
        auto brute_force = [&]()->void{
            
        };
        // brute_force();
        // break;
#endif
    }

    cerr << "[time:" << 1.0*clock()/CLOCKS_PER_SEC << "s] ";
    return 0;
}


/*
-> Please, don't get stuck at one approach only.
-> Understood the problem?, misread?
-> edge cases, n = 1 ?
-> binary search ?
-> brute_force ?
-> time complexity - 1 sec : 4e8 will work but risky.
-> space complexity - 256 mb : 6e7(int), 3e7(ll), 2e8(bool, char), will work.
-> entire input - multiple testcases.
-> mod : sort ?, mint, remove #define int.
-> Iterative > Recursive.
-> clear - global variables.
-> builtin function - add ll.
-> Move on - if completely_stuck > 30 minute.
-> Submit - right file.
*/

/*
-> Don't assume blindly.
-> Focus on problem.
-> Recovery from the failure.
-> Do consider worst case time complexity.
-> If solution is barely passing then do submit again after doing optimization.
-> Be carefull in nested loop. Iterating variable name should be different for both loop.
-> Think simple first.
-> Don't be stupid.
-> Be comfortable and in your control.
*/