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 <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){
	return o<<"("<<p.fs<<","<<p.sc<<")";
}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){
	o<<"{";
	for(const T& v:vc) o<<v<<",";
	o<<"}";
	return o;
}
using ll = long long;
template<class T> using V = vector<T>;
template<class T> using VV = vector<vector<T>>;
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); }

#ifdef LOCAL
#define show(x) cerr << "LINE" << __LINE__ << " : " << #x << " = " << (x) << endl
#define dump(x) cerr << "LINE" << __LINE__ << " : " << #x << " = {";  \
	for(auto v: x) cerr << v << ","; cerr << "}" << endl;
#else
#define show(x) true
#define dump(x) true
#endif
template<unsigned int mod_>
struct ModInt{
	using uint = unsigned int;
	using ll = long long;
	using ull = unsigned long long;

	constexpr static uint mod = mod_;

	uint v;
	ModInt():v(0){}
	ModInt(ll _v):v(normS(_v%mod+mod)){}
	explicit operator bool() const {return v!=0;}
	static uint normS(const uint &x){return (x<mod)?x:x-mod;}		// [0 , 2*mod-1] -> [0 , mod-1]
	static ModInt make(const uint &x){ModInt m; m.v=x; return m;}
	ModInt operator+(const ModInt& b) const { return make(normS(v+b.v));}
	ModInt operator-(const ModInt& b) const { return make(normS(v+mod-b.v));}
	ModInt operator-() const { return make(normS(mod-v)); }
	ModInt operator*(const ModInt& b) const { return make((ull)v*b.v%mod);}
	ModInt operator/(const ModInt& b) const { return *this*b.inv();}
	ModInt& operator+=(const ModInt& b){ return *this=*this+b;}
	ModInt& operator-=(const ModInt& b){ return *this=*this-b;}
	ModInt& operator*=(const ModInt& b){ return *this=*this*b;}
	ModInt& operator/=(const ModInt& b){ return *this=*this/b;}
	ModInt& operator++(int){ return *this=*this+1;}
	ModInt& operator--(int){ return *this=*this-1;}
	ll extgcd(ll a,ll b,ll &x,ll &y) const{
		ll p[]={a,1,0},q[]={b,0,1};
		while(*q){
			ll t=*p/ *q;
			rep(i,3) swap(p[i]-=t*q[i],q[i]);
		}
		if(p[0]<0) rep(i,3) p[i]=-p[i];
		x=p[1],y=p[2];
		return p[0];
	}
	ModInt inv() const {
		ll x,y;
		extgcd(v,mod,x,y);
		return make(normS(x+mod));
	}
	ModInt pow(ll p) const {
		if(p<0) return inv().pow(-p);
		ModInt a = 1;
		ModInt x = *this;
		while(p){
			if(p&1) a *= x;
			x *= x;
			p >>= 1;
		}
		return a;
	}
	bool operator==(const ModInt& b) const { return v==b.v;}
	bool operator!=(const ModInt& b) const { return v!=b.v;}
	friend istream& operator>>(istream &o,ModInt& x){
		ll tmp;
		o>>tmp;
		x=ModInt(tmp);
		return o;
	}
	friend ostream& operator<<(ostream &o,const ModInt& x){ return o<<x.v;}
};
using mint = ModInt<998244353>;

V<mint> fact,ifact;
mint Choose(int a,int b){
	if(b<0 || a<b) return 0;
	return fact[a] * ifact[b] * ifact[a-b];
}
void InitFact(int N){
	fact.resize(N);
	ifact.resize(N);
	fact[0] = 1;
	rep1(i,N-1) fact[i] = fact[i-1] * i;
	ifact[N-1] = fact[N-1].inv();
	for(int i=N-2;i>=0;i--) ifact[i] = ifact[i+1] * (i+1);
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);		//DON'T USE scanf/printf/puts !!
	cout << fixed << setprecision(20);
	InitFact(10000);

	int H,W; cin >> H >> W;
	V<string> S(H); rep(i,H) cin >> S[i];

	mint dp[3][11][11][11][11] = {};
	bool done[3][11][11][11][11] = {};
	function<mint(int,int,int,int,int)> rec = [&](int c,int h,int w,int bh,int bw){
		if(h < bh || w < bw) return mint(0);
		if(h == bh && w == bw) return mint(1);
		if(done[c][h][w][bh][bw]) return dp[c][h][w][bh][bw];
		mint& res = dp[c][h][w][bh][bw];
		if(c == 1){
			rep1(i,w-bw){
				res += rec(1,w-i,h,bw,bh) * Choose(w-bw,i);
			}
		}else{
			rep1(i,w-bw) rep1(j,w-bw-i){
				res += rec(2,w-i-j,h,bw,bh) * Choose(w-bw,i)*Choose(w-bw-i,j);
			}
			res += rec(1,h,w,bh,bw)*2;
		}
		done[c][h][w][bh][bw] = true;
		return res;
	};
	VV<mint> f(H+1,V<mint>(W+1));
	rep1(bh,H) rep1(bw,W){
		rep(i,W-bw+1) rep(j,W-bw-i+1){
			f[bh][bw] += rec(2,W-i-j,H,bw,bh) * Choose(W-bw,i) * Choose(W-bw-i,j);
		}
	}
	{
		VV<mint> p = {
			{0,0,0,0,0,0,0,0,0,0,0},
			{0,2,4,8,16,32,64,128,256,512,1024},
			{0,4,14,46,146,454,1394,4246,12866,38854,117074},
			{0,8,46,230,1066,4718,20266,85310,354106,1455278,5938186},
			{0,16,146,1066,6902,41506,237686,1315666,7107302,37712866,197451926},
			{0,32,454,4718,41506,329462,2441314,17234438,117437746,779305142,76485309},
			{0,64,1394,20266,237686,2441314,22934774,202229266,703495653,844104725,406231977},
			{0,128,4246,85310,1315666,17234438,202229266,197176084,485832140,67048938,969814099},
			{0,256,12866,354106,7107302,117437746,703495653,485832140,539393474,598139740,429708905},
			{0,512,38854,1455278,37712866,779305142,844104725,67048938,598139740,555407722,910838124},
			{0,1024,117074,5938186,197451926,76485309,406231977,969814099,429708905,910838124,710838430}
			};
		f[0][0] = p[H][W];
	}
	show(f);
	mint ans = 0;
	rep(s,1<<H) rep(t,1<<W){
		int ha=0,hb=0,wa=0,wb=0;
		rep(i,H) if((s>>i)&1){
			rep(j,W) if((t>>j)&1){
				if(S[i][j] == '#') ha |= 1<<i, wa |= 1<<j;
				else hb |= 1<<i, wb |= 1<<j;
			}
		}
		if(s == ha && s == hb && t == wa && t == wb){
			show(s);show(t);show("----------------");
			ans += f[__builtin_popcount(s)][__builtin_popcount(t)];
		}
	}
	cout << ans << endl;
}