Problem: We have an H \times W grid, where each square is painted white or black in the initial state. Given are strings A_1, A_2, ..., A_H representing the colors of the squares in the initial state. For each pair (i, j) (1 \leq i \leq H, 1 \leq j \leq W), if the j-th character of A_i is `.`, the square at the i-th row and j-th column is painted white; if that character is `#`, that square is painted black.

Among the 2^{HW} ways for each square in the grid to be painted white or black, how many can be obtained from the initial state by performing the operations below any number of times (possibly zero) in any order? Find this count modulo 998,244,353.

* Choose one row, then paint all the squares in that row white.
* Choose one row, then paint all the squares in that row black.
* Choose one column, then paint all the squares in that column white.
* Choose one column, then paint all the squares in that column black.

Constraints

* 1 \leq H, W \leq 10
* |A_i| = W (1 \leq i \leq H)
* All strings A_i consist of `.` and `#`.
* H and W are integers.

Input

Input is given from Standard Input in the following format:


H W
A_1
A_2
\vdots
A_H


Output

Print the answer.

Examples

Input

2 2
#.
.#


Output

15


Input

2 2
.
.#


Output

15


Input

3 3
...
...
...


Output

230


Input

2 4
...
...#


Output

150


Input

6 7
.......
.......
.#.....
..#....
.#.#...
.......


Output

203949910

Solution (in CPP):

Solution:
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <random>
 
using namespace std;
template<typename T1, typename T2>inline void chkmin(T1 &x, T2 y) { if (x > y) x = y; }
template<typename T1, typename T2>inline void chkmax(T1 &x, T2 y) { if (x < y) x = y; }
#define sz(c) (int)(c).size()
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define left left228
#define right right228
#define rank rank228
#define y1 y1228
#define read(FILENAME) freopen((FILENAME + ".in").c_str(), "r", stdin)
#define write(FILENAME) freopen((FILENAME + ".out").c_str(), "w", stdout)
#define files(FILENAME) read(FILENAME), write(FILENAME)
#define pb push_back
#define mp make_pair
using ll = long long;
using ld = long double;
// const int MAXMEM = 200 * 1000 * 1024;
// char _memory[MAXMEM];
// size_t _ptr = 0;
// void* operator new(size_t _x) { _ptr += _x; return _memory + _ptr - _x; }
// void operator delete (void*) noexcept {}
const string FILENAME = "input";
const int Mod = 998244353;
const int MAXN = 10;
const int MAXM = 1 << MAXN;

int h, w;
string s[MAXN];
 

int summ(int a, int b) {
    int res = a + (b < 0 ? b + Mod: b);
    return (res >= Mod ? res - Mod: res);
}


int col[MAXN][MAXN];
int dp[MAXM][MAXM];
int keks[MAXM * MAXM][2 * MAXN + 1];
 

bool check(int m0, int m1) {
    vector<int> rc(MAXN, 0), cc(MAXN, 0);
    for (int y = 0; y < MAXN; y++) {
        if (!(m0 & (1 << y))) {
            rc[y] = 3;
        }
    }
    for (int x = 0; x < MAXN; x++) {
        if (!(m1 & (1 << x))) {
            cc[x] = 3;
        }
    }
    for (int y = 0; y < MAXN; y++) {
        if (!(m0 & (1 << y))) {
            continue;
        }
        for (int x = 0; x < MAXN; x++) {
            if (!(m1 & (1 << x))) {
                continue;
            }
            rc[y] |= col[y][x];
            cc[x] |= col[y][x];
        }
    }
    bool works = true;
    for (auto v: rc) {
        works &= (v == 3);
    }
    for (auto v: cc) {
        works &= (v == 3);
    }
    return works;
}
 

int keksum(int m0, int m1) {
    int m = m0 | (m1 << MAXN);
    keks[m][2 * MAXN] = dp[m0][m1];
    for (int j = 2 * MAXN - 1; j >= 0; j--) {
        if (m & (1 << j)) {
            keks[m][j] =    summ(keks[m][j + 1], -keks[m ^ (1 << j)][j + 1]);
        } else {
            keks[m][j] = keks[m][j + 1];
        }
    }
    return keks[m][0];
}


void setdp(int m0, int m1, int val) {
    dp[m0][m1] = val;
    keksum(m0, m1);
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //read(FILENAME);     
    cin >> h >> w;
    for (int i = 0; i < h; i++) {
        cin >> s[i];
    }
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            col[i][j] = 1 + (s[i][j] == '#');
        }
    }
    int h0 = 1 << h;
    int h1 = 1 << w;
    for (int m0 = 0; m0 < h0; m0++) {
        setdp(m0, 0, 1);
    }
    for (int m1 = 0; m1 < h1; m1++) {
        setdp(0, m1, 1);
    }
    for (int m0 = 0; m0 < h0; m0++) {
        int rc = __builtin_popcount(m0);
        if (rc == 0) {
            continue;
        }
        for (int m1 = 0; m1 < h1; m1++) {
            int cc = __builtin_popcount(m1);
            if (cc == 0) {
                continue;
            }
            int res = check(m0, m1);
            for (int s0 = m0; ; s0 = (s0 - 1) & m0) {
                int pw = rc - __builtin_popcount(s0);
                if (pw > 1) {
                    ll mult = (ll)(pw & 1 ? 1: Mod - 1) * ((1 << pw) - 2) % Mod;
                    res = (res + (ll)mult * dp[s0][m1]) % Mod;
                }
                if (s0 == 0) {
                    break;
                }
            }
            for (int s1 = m1; ; s1 = (s1 - 1) & m1) {
                int pw = cc - __builtin_popcount(s1);
                if (pw > 1) {
                    ll mult = (ll)(pw & 1 ? 1: Mod - 1) * ((1 << pw) - 2) % Mod;
                    res = (res + (ll)mult * dp[m0][s1]) % Mod;
                }
                if (s1 == 0) {
                    break;
                }
            }
            int add = Mod - keksum(m0, m1);
            add = summ(add, add);
            res = summ(res, add);
            setdp(m0, m1, res);
        }
    }
    cout << dp[h0 - 1][h1 - 1] << '\n';
    return 0;
}