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:
//https://betrue12.hateblo.jp/entry/2020/01/19/170701
//https://drken1215.hatenablog.com/entry/2020/02/02/134400

#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;
#define chmax(x,y) x = max(x,y)
#define chmin(x,y) x = min(x,y)

const int mod = 998244353;
struct mint {
ll x; 
mint(ll x=0):x((x%mod+mod)%mod){}
mint operator-() const { return mint(-x);}
mint& operator+=(const mint a) {
if ((x += a.x) >= mod) x -= mod;
return *this;
 }
mint& operator-=(const mint a) {
if ((x += mod-a.x) >= mod) x -= mod;
return *this;
 }
 mint& operator*=(const mint a) {
(x *= a.x) %= mod;
return *this;
}
mint operator+(const mint a) const {
mint res(*this);
return res+=a;
}
mint operator-(const mint a) const {
mint res(*this);
return res-=a;
}
 mint operator*(const mint a) const {
mint res(*this);
return res*=a;
}
mint pow(ll t) const {
if (!t) return 1;
mint a = pow(t>>1);
a *= a;
if (t&1) a *= *this;
return a;
}
 mint inv() const {
return pow(mod-2);
 }
  mint& operator/=(const mint a) {
return (*this) *= a.inv();
 }
mint operator/(const mint a) const {
mint res(*this);
return res/=a;
 }
};
struct combination {
vector<mint> fact, ifact;
combination(int n):fact(n+1),ifact(n+1) {
  assert(n < mod);
 fact[0] = 1;
 for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
 ifact[n] = fact[n].inv();
  for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
}
mint operator()(int n, int k) {
if (k < 0 || k > n) return 0;
return fact[n]*ifact[k]*ifact[n-k];
}
  };

int H,W;
vector<string>A;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);

//初始化排列组合

combination c(20);
cin>>H>>W;
A.resize(H);
rep(h,H)cin>>A[h];

/*
dp计算长方形的组合数
dp1[a][b]表示长方形里有黑色线的组合数
dp2[a][b]表示长方形里有黑色线的组合数

横的有i个白线,竖的有j个白线的时候
i和j必须大于0 
dp2[a][b]+=c(a,i)*c(b,j)*dp2[a-i][b-j](1<=i<=a-1,1<=j<=b-1) 
dp2[a][b]+=1 (全白的情况有一种)

横的有i个黑线，竖的有j个黑线的时候
i和j不能同时为0
dp1[a][b]+=c(a,i)*c(b,j)*dp2[a-i][b-j] (i+j>=1,i<=a-1,j<=b-1)
dp1[a][b]+=1(全黑的情况有一种)
*/
vector<vector<mint>>R(15,vector<mint>(15,0));
auto dp1=R;
auto dp2=R;
rep(i,15)R[0][i]=R[i][0]=mint(2).pow(i);

//计算dp2

for(int a=1;a<15;a++)
    for(int b=1;b<15;b++){
        dp2[a][b]=1;
        for(int i=1;i<a;i++)
            for(int j=1;j<b;j++){
                dp2[a][b]+=dp2[a-i][b-j]*c(a,i)*c(b,j);
            }
    }
//计算dp1

for(int a=1;a<15;a++){
    for(int b=1;b<15;b++){
        dp1[a][b]=1;
        for(int i=0;i<a;i++)
            for(int j=0;j<b;j++){
                if(i+j==0)continue;
                dp1[a][b]+=dp2[a-i][b-j]*c(a,i)*c(b,j);
            }
        R[a][b]=dp1[a][b]+dp2[a][b];
    }
}

/*
计算L的组合数
sumR[a][b] 表示两个交叉矩形的组合数的和
subR[a][b]表示竖的a个黑色横着b个白色的长方形组合数(先涂黑色)
这里subR[a][b]=subR[b][a] 
*/
vector<vector<mint>>L(15,vector<mint>(15,0));
auto sumR=L,subR=L;
rep(i,15){
    subR[1][i]=1;
    subR[i][1]=mint(2).pow(i)-1;
}
for(int s=2;s<30;s++){
    for(int a=1;a<15;a++){
        int b=s-a;
        if(b<1||b>=15)continue;
        subR[a][b]=1;
        for(int i=1;i<a;i++){
            subR[a][b]+=c(a,i)*subR[b][a-i];//？
        }
    }
}

rep(a,15)rep(b,15){
    if(a==0)sumR[a][b]=1;
    else if(b==0)sumR[a][b]=1;
    else sumR[a][b]=subR[a][b]+subR[b][a];
}
//竖方向黑色i个白色a-i个，横方向白色j个黑色b-j个 求i*j的长方形颜色组合数
rep(i,15)L[0][i]=L[i][0]=mint(2).pow(i);
for(int a=1;a<14;a++)
    for(int b=1;b<14;b++)
        rep(i,a+1)
            rep(j,b+1){
                L[a][b]+=c(a,i)*c(b,j)*sumR[i][j]*sumR[a-i][b-j];
            }


    mint ans = R[H][W];
    for (int bit = 0; bit < (1<<H)-1; ++bit) {
        vector<int> tate;
        for (int i = 0; i < H; ++i) if (!(bit & (1<<i))) tate.push_back(i);
        for (int bit2 = 0; bit2 < (1<<W)-1; ++bit2) {
            vector<int> yoko;
            for (int i = 0; i < W; ++i) if (!(bit2 & (1<<i))) yoko.push_back(i);
 
            //留下来的行或者列必须有两种颜色
            bool ok = true;
            for (auto i : tate) {
                set<char> se;
                for (auto j : yoko) se.insert(A[i][j]);
                if (se.size() != 2) ok = false;
            }
            for (auto j : yoko) {
                set<char> se;
                for (auto i : tate) se.insert(A[i][j]);
                if (se.size() != 2) ok = false;
            }
 
            if (ok) {
                int c = __builtin_popcount(bit);
                int r = __builtin_popcount(bit2);
                mint add = L[c][r];
                ans += add;
            }
        }
    }
    cout << ans.x << endl;
return 0;
}