#include <bits/stdc++.h>
using namespace std;
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define IFOR(i, begin, end) for(int i=(end)-1;i>=(begin);i--)
#define IREP(i, n) IFOR(i,0,n)
#define Sort(v) sort(v.begin(), v.end())
#define Reverse(v) reverse(v.begin(), v.end())
#define all(v) v.begin(),v.end()
#define SZ(v) ((int)v.size())
#define Lower_bound(v, x) distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) distance(v.begin(), upper_bound(v.begin(), v.end(), x))
#define Max(a, b) a = max(a, b)
#define Min(a, b) a = min(a, b)
#define bit(n) (1LL<<(n))
#define debug(x) cout << #x << "=" << x << endl;
#define vdebug(v) { cout << #v << "=" << endl; REP(i_debug, v.size()){ cout << v[i_debug] << ","; } cout << endl; }
#define mdebug(m) { cout << #m << "=" << endl; REP(i_debug, m.size()){ REP(j_debug, m[i_debug].size()){ cout << m[i_debug][j_debug] << ","; } cout << endl;} }
#define Return(ans) { cout << (ans) << endl; return 0; }
#define pb push_back
#define fi first
#define se second
#define int long long
#define INF 1000000000000000000
template<typename T> istream &operator>>(istream &is, vector<T> &v){ for (auto &x : v) is >> x; return is; }
template<typename T> ostream &operator<<(ostream &os, vector<T> &v){ for(int i = 0; i < v.size(); i++) { cout << v[i]; if(i != v.size() - 1) cout << endl; }; return os; }
template<typename T1, typename T2> ostream &operator<<(ostream &os, pair<T1, T2> p){ cout << '(' << p.first << ',' << p.second << ')'; return os; }
template<typename T> void Out(T x) { cout << x << endl; }
template<typename T1, typename T2> void Ans(bool f, T1 y, T2 n) { if(f) Out(y); else Out(n); }

using vec = vector<int>;
using mat = vector<vec>;
using Pii = pair<int, int>;
using v_bool = vector<bool>;
using v_Pii = vector<Pii>;

//int dx[4] = {1,0,-1,0};
//int dy[4] = {0,1,0,-1};
//char d[4] = {'D','R','U','L'};

//const int mod = 1000000007;
const int mod = 998244353;

template<long long MOD>
struct ModInt{

    using ll = long long;
    ll val;

    void setval(ll v) { val = v % MOD; };
    ModInt(): val(0) {}
    ModInt(ll v) { setval(v); };

    ModInt operator+(const ModInt &x) const { return ModInt(val + x.val); }
    ModInt operator-(const ModInt &x) const { return ModInt(val - x.val + MOD); }
    ModInt operator*(const ModInt &x) const { return ModInt(val * x.val); }
    ModInt operator/(const ModInt &x) const { return *this * x.inv(); }
    ModInt operator-() const { return ModInt(MOD - val); }
    ModInt operator+=(const ModInt &x) { return *this = *this + x; }
    ModInt operator-=(const ModInt &x) { return *this = *this - x; }
    ModInt operator*=(const ModInt &x) { return *this = *this * x; }
    ModInt operator/=(const ModInt &x) { return *this = *this / x; }

    friend ostream& operator<<(ostream &os, const ModInt &x) { os << x.val; return os; }
    friend istream& operator>>(istream &is, ModInt &x) { is >> x.val; x.val = (x.val % MOD + MOD) % MOD; return is; }

    ModInt pow(ll n) const {
        ModInt a = 1;
        if(n == 0) return a;
        int i0 = 64 - __builtin_clzll(n);
        for(int i = i0 - 1; i >= 0; i--){
            a = a * a;
            if((n >> i) & 1) a *= (*this); 
        }
        return a;
    }
    ModInt inv() const { return this->pow(MOD - 2); }
};

using mint = ModInt<mod>; mint pow(mint x, long long n) { return x.pow(n); }
//using mint = double; //for debug
using mvec = vector<mint>;
using mmat = vector<mvec>;

struct Combination{

    vector<mint> fact, invfact;

    Combination(int N){
        fact = vector<mint>({mint(1)});
        invfact = vector<mint>({mint(1)});
        fact_initialize(N);
    }

    void fact_initialize(int N){
        int i0 = fact.size();
        if(i0 >= N + 1) return;
        fact.resize(N + 1);
        invfact.resize(N + 1);
        for(int i = i0; i <= N; i++) fact[i] = fact[i - 1] * i;
        invfact[N] = (mint)1 / fact[N];
        for(int i = N - 1; i >= i0; i--) invfact[i] = invfact[i + 1] * (i + 1); 
    }

    mint nCr(int n, int r){
        if(n < 0 || r < 0 || r > n) return mint(0);
        if(fact.size() < n + 1) fact_initialize(n);
        return fact[n] * invfact[r] * invfact[n - r];
    }

    mint nPr(int n, int r){
        if(n < 0 || r < 0 || r > n) return mint(0);
        if(fact.size() < n + 1) fact_initialize(n);
        return fact[n] * invfact[n - r];
    }

    mint Catalan(int n){
        if(n < 0) return 0;
        else if(n == 0) return 1;
        if(fact.size() < 2 * n + 1) fact_initialize(2 * n);
        return fact[2 * n] * invfact[n + 1] * invfact[n];
    }

};

signed main(){

    int H, W; cin >> H >> W;
    vector<string> A(H); cin >> A;
    Combination C(H + W);
    
    mmat dp1(H + 1, mvec(W + 1)), dp2(H + 1, mvec(W + 1));
    REP(h, H + 1) REP(w, W + 1){
        dp1[h][w] = 1;
        FOR(i, 0, h) FOR(j, 0, w) if(i + j > 0) dp1[h][w] += dp2[h - i][w - j] * C.nCr(h, i) * C.nCr(w, j);

        dp2[h][w] = 1;
        FOR(i, 1, h) FOR(j, 1, w) dp2[h][w] += dp2[h - i][w - j] * C.nCr(h, i) * C.nCr(w, j);
    }
    REP(h, H + 1) REP(w, W + 1) dp1[h][w] += dp2[h][w];

    mmat dq1(H + 1, mvec(W + 1)), dq2(H + 1, mvec(W + 1));
    REP(h, H + 1) REP(w, W + 1){
        dq1[h][w] = 1;
        FOR(i, 1, h) dq1[h][w] += dq2[h - i][w] * C.nCr(h, i);

        dq2[h][w] = 1;
        FOR(j, 1, w) dq2[h][w] += dq1[h][w - j] * C.nCr(w, j);
    }
    REP(h, H + 1) REP(w, W + 1) dq1[h][w] += dq2[h][w];
    REP(h, H) dq1[h][0] = 1;
    REP(w, W) dq1[0][w] = 1;

    mmat dr(H, mvec(W, 0));
    REP(h, H) REP(w, W){
        FOR(i, 0, h + 1) FOR(j, 0, w + 1) dr[h][w] += dq1[i][w - j] * dq1[h - i][j] * C.nCr(h, i) * C.nCr(w, j);  
    }

    vector<v_bool> same_x(bit(H), v_bool(W, true)), same_y(bit(W), v_bool(H, true));
    REP(x, bit(H)) REP(j, W){
        REP(i1, H) REP(i2, i1) if((x >> i1) & (x >> i2) & 1){
            if(A[i1][j] != A[i2][j]) same_x[x][j] = false;
        }
    }
    REP(y, bit(W)) REP(i, H){
        REP(j1, W) REP(j2, j1) if((y >> j1) & (y >> j2) & 1){
            if(A[i][j1] != A[i][j2]) same_y[y][i] = false;
        }
    }

    mint ans = dp1[H][W];
    REP(x, bit(H)) REP(y, bit(W)){
        bool ok = true;
        REP(i, H) if(((x >> i) & 1) && same_y[y][i]) ok = false;
        REP(j, W) if(((y >> j) & 1) && same_x[x][j]) ok = false;
        if(ok){
            int h = H - __builtin_popcountll(x), w = W - __builtin_popcountll(y);
            if(h < H && w < W) ans += dr[h][w];
        }
    }
    Out(ans);

    return 0;
}

### Prompt

In cpp, your task is to solve the following 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

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define IFOR(i, begin, end) for(int i=(end)-1;i>=(begin);i--)
#define IREP(i, n) IFOR(i,0,n)
#define Sort(v) sort(v.begin(), v.end())
#define Reverse(v) reverse(v.begin(), v.end())
#define all(v) v.begin(),v.end()
#define SZ(v) ((int)v.size())
#define Lower_bound(v, x) distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) distance(v.begin(), upper_bound(v.begin(), v.end(), x))
#define Max(a, b) a = max(a, b)
#define Min(a, b) a = min(a, b)
#define bit(n) (1LL<<(n))
#define debug(x) cout << #x << "=" << x << endl;
#define vdebug(v) { cout << #v << "=" << endl; REP(i_debug, v.size()){ cout << v[i_debug] << ","; } cout << endl; }
#define mdebug(m) { cout << #m << "=" << endl; REP(i_debug, m.size()){ REP(j_debug, m[i_debug].size()){ cout << m[i_debug][j_debug] << ","; } cout << endl;} }
#define Return(ans) { cout << (ans) << endl; return 0; }
#define pb push_back
#define fi first
#define se second
#define int long long
#define INF 1000000000000000000
template<typename T> istream &operator>>(istream &is, vector<T> &v){ for (auto &x : v) is >> x; return is; }
template<typename T> ostream &operator<<(ostream &os, vector<T> &v){ for(int i = 0; i < v.size(); i++) { cout << v[i]; if(i != v.size() - 1) cout << endl; }; return os; }
template<typename T1, typename T2> ostream &operator<<(ostream &os, pair<T1, T2> p){ cout << '(' << p.first << ',' << p.second << ')'; return os; }
template<typename T> void Out(T x) { cout << x << endl; }
template<typename T1, typename T2> void Ans(bool f, T1 y, T2 n) { if(f) Out(y); else Out(n); }

using vec = vector<int>;
using mat = vector<vec>;
using Pii = pair<int, int>;
using v_bool = vector<bool>;
using v_Pii = vector<Pii>;

//int dx[4] = {1,0,-1,0};
//int dy[4] = {0,1,0,-1};
//char d[4] = {'D','R','U','L'};

//const int mod = 1000000007;
const int mod = 998244353;

template<long long MOD>
struct ModInt{

    using ll = long long;
    ll val;

    void setval(ll v) { val = v % MOD; };
    ModInt(): val(0) {}
    ModInt(ll v) { setval(v); };

    ModInt operator+(const ModInt &x) const { return ModInt(val + x.val); }
    ModInt operator-(const ModInt &x) const { return ModInt(val - x.val + MOD); }
    ModInt operator*(const ModInt &x) const { return ModInt(val * x.val); }
    ModInt operator/(const ModInt &x) const { return *this * x.inv(); }
    ModInt operator-() const { return ModInt(MOD - val); }
    ModInt operator+=(const ModInt &x) { return *this = *this + x; }
    ModInt operator-=(const ModInt &x) { return *this = *this - x; }
    ModInt operator*=(const ModInt &x) { return *this = *this * x; }
    ModInt operator/=(const ModInt &x) { return *this = *this / x; }

    friend ostream& operator<<(ostream &os, const ModInt &x) { os << x.val; return os; }
    friend istream& operator>>(istream &is, ModInt &x) { is >> x.val; x.val = (x.val % MOD + MOD) % MOD; return is; }

    ModInt pow(ll n) const {
        ModInt a = 1;
        if(n == 0) return a;
        int i0 = 64 - __builtin_clzll(n);
        for(int i = i0 - 1; i >= 0; i--){
            a = a * a;
            if((n >> i) & 1) a *= (*this); 
        }
        return a;
    }
    ModInt inv() const { return this->pow(MOD - 2); }
};

using mint = ModInt<mod>; mint pow(mint x, long long n) { return x.pow(n); }
//using mint = double; //for debug
using mvec = vector<mint>;
using mmat = vector<mvec>;

struct Combination{

    vector<mint> fact, invfact;

    Combination(int N){
        fact = vector<mint>({mint(1)});
        invfact = vector<mint>({mint(1)});
        fact_initialize(N);
    }

    void fact_initialize(int N){
        int i0 = fact.size();
        if(i0 >= N + 1) return;
        fact.resize(N + 1);
        invfact.resize(N + 1);
        for(int i = i0; i <= N; i++) fact[i] = fact[i - 1] * i;
        invfact[N] = (mint)1 / fact[N];
        for(int i = N - 1; i >= i0; i--) invfact[i] = invfact[i + 1] * (i + 1); 
    }

    mint nCr(int n, int r){
        if(n < 0 || r < 0 || r > n) return mint(0);
        if(fact.size() < n + 1) fact_initialize(n);
        return fact[n] * invfact[r] * invfact[n - r];
    }

    mint nPr(int n, int r){
        if(n < 0 || r < 0 || r > n) return mint(0);
        if(fact.size() < n + 1) fact_initialize(n);
        return fact[n] * invfact[n - r];
    }

    mint Catalan(int n){
        if(n < 0) return 0;
        else if(n == 0) return 1;
        if(fact.size() < 2 * n + 1) fact_initialize(2 * n);
        return fact[2 * n] * invfact[n + 1] * invfact[n];
    }

};

signed main(){

    int H, W; cin >> H >> W;
    vector<string> A(H); cin >> A;
    Combination C(H + W);
    
    mmat dp1(H + 1, mvec(W + 1)), dp2(H + 1, mvec(W + 1));
    REP(h, H + 1) REP(w, W + 1){
        dp1[h][w] = 1;
        FOR(i, 0, h) FOR(j, 0, w) if(i + j > 0) dp1[h][w] += dp2[h - i][w - j] * C.nCr(h, i) * C.nCr(w, j);

        dp2[h][w] = 1;
        FOR(i, 1, h) FOR(j, 1, w) dp2[h][w] += dp2[h - i][w - j] * C.nCr(h, i) * C.nCr(w, j);
    }
    REP(h, H + 1) REP(w, W + 1) dp1[h][w] += dp2[h][w];

    mmat dq1(H + 1, mvec(W + 1)), dq2(H + 1, mvec(W + 1));
    REP(h, H + 1) REP(w, W + 1){
        dq1[h][w] = 1;
        FOR(i, 1, h) dq1[h][w] += dq2[h - i][w] * C.nCr(h, i);

        dq2[h][w] = 1;
        FOR(j, 1, w) dq2[h][w] += dq1[h][w - j] * C.nCr(w, j);
    }
    REP(h, H + 1) REP(w, W + 1) dq1[h][w] += dq2[h][w];
    REP(h, H) dq1[h][0] = 1;
    REP(w, W) dq1[0][w] = 1;

    mmat dr(H, mvec(W, 0));
    REP(h, H) REP(w, W){
        FOR(i, 0, h + 1) FOR(j, 0, w + 1) dr[h][w] += dq1[i][w - j] * dq1[h - i][j] * C.nCr(h, i) * C.nCr(w, j);  
    }

    vector<v_bool> same_x(bit(H), v_bool(W, true)), same_y(bit(W), v_bool(H, true));
    REP(x, bit(H)) REP(j, W){
        REP(i1, H) REP(i2, i1) if((x >> i1) & (x >> i2) & 1){
            if(A[i1][j] != A[i2][j]) same_x[x][j] = false;
        }
    }
    REP(y, bit(W)) REP(i, H){
        REP(j1, W) REP(j2, j1) if((y >> j1) & (y >> j2) & 1){
            if(A[i][j1] != A[i][j2]) same_y[y][i] = false;
        }
    }

    mint ans = dp1[H][W];
    REP(x, bit(H)) REP(y, bit(W)){
        bool ok = true;
        REP(i, H) if(((x >> i) & 1) && same_y[y][i]) ok = false;
        REP(j, W) if(((y >> j) & 1) && same_x[x][j]) ok = false;
        if(ok){
            int h = H - __builtin_popcountll(x), w = W - __builtin_popcountll(y);
            if(h < H && w < W) ans += dr[h][w];
        }
    }
    Out(ans);

    return 0;
}

```