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 <vector>
#include <algorithm>
using namespace std;

// 解説 AC（75% 自力）

long long mod = 998244353;
long long H, W;
long long bitcnt[1 << 10];
long long fact[19];
long long nr[19][19];
long long dp0[19][19]; // 何もない状態
long long dp1[19][19]; // 横方向のみある
long long dp2[19][19]; // 縦方向のみある
long long dp3[19][19]; // 両方向ある
bool used[1 << 10][1 << 10];
bool vis[1 << 10][1 << 10];
char c[19][19];

void init() {
	fact[0] = 1;
	for (int i = 1; i <= 15; i++) fact[i] = 1LL * i * fact[i - 1];
	for (int i = 0; i <= 15; i++) {
		for (int j = 0; j <= 15; j++) {
			if (i == 0 || j == 0) nr[i][j] = 1;
			else nr[i][j] = (nr[i - 1][j] + nr[i][j - 1]) % mod;
		}
	}
	for (int i = 0; i < (1 << 10); i++) {
		for (int j = 0; j < 10; j++) bitcnt[i] += (i / (1 << j)) % 2;
	}
}

long long ncr(int n, int r) {
	if (r < 0 || n < r) return 0;
	return nr[n - r][r];
}

vector<int> VecToVec2(int h, int w, vector<int> vec) {
	vector<int> vec2(h, 0);
	for (int i = 0; i < vec.size(); i++) {
		if (vec[i] >= 1) vec2[vec[i] - 1] += 1;
	}
	for (int i = h - 1; i >= 1; i--) vec2[i - 1] += vec2[i];
	return vec2;
}

long long calc_0(int h, int w, vector<int> vec) {
	vector<int> vec2 = VecToVec2(h, w, vec);
	long long cnt = 1, val = fact[h] * fact[w];
	for (int i = 1; i < vec.size(); i++) {
		if (vec[i] == vec[i - 1]) cnt++;
		else cnt = 1;
		val /= cnt;
	}
	cnt = 1;
	for (int i = 1; i < vec2.size(); i++) {
		if (vec2[i] == vec2[i - 1]) cnt++;
		else cnt = 1;
		val /= cnt;
	}
	return val;
}

long long calc_1(int h, int w, vector<int> vec) {
	vector<int> vec2 = VecToVec2(h, w, vec);
	long long ret = 2, cnt = 1;
	if (vec2.size() == 0) ret = 1;
	for (int i = 1; i < vec2.size(); i++) {
		if (vec2[i - 1] == vec2[i]) cnt++;
		if (vec2[i - 1] != vec2[i]) {
			ret += ((1LL << cnt) - 1LL);
			cnt = 1;
		}
	}
	ret += ((1LL << cnt) - 2LL);
	return ret;
}

long long calc_2(int h, int w, vector<int> vec) {
	long long ret = 2, cnt = 1;
	if (vec.size() == 0) ret = 1;
	for (int i = 1; i < vec.size(); i++) {
		if (vec[i - 1] == vec[i]) cnt++;
		if (vec[i - 1] != vec[i]) {
			ret += ((1LL << cnt) - 1LL);
			cnt = 1;
		}
	}
	ret += ((1LL << cnt) - 2LL);
	return ret;
}

void solve(int h, int w, vector<int> vec) {
	if (vec.size() == w) {
		dp0[h][w] += calc_0(h, w, vec);
		dp1[h][w] += calc_0(h, w, vec) * calc_1(h, w, vec);
		dp2[h][w] += calc_0(h, w, vec) * calc_2(h, w, vec);
		dp3[h][w] += calc_0(h, w, vec) * (calc_1(h, w, vec) + calc_2(h, w, vec) - 1LL);
		dp0[h][w] = (dp0[h][w] + mod * mod) % mod;
		dp1[h][w] = (dp1[h][w] + mod * mod) % mod;
		dp2[h][w] = (dp2[h][w] + mod * mod) % mod;
		dp3[h][w] = (dp3[h][w] + mod * mod) % mod;
		return;
	}

	int border = h;
	if (vec.size() >= 1) border = vec[vec.size() - 1];
	for (int i = 0; i <= border; i++) {
		vector<int> vec2 = vec;
		vec2.push_back(i);
		solve(h, w, vec2);
	}
}

bool dfs(int posx, int posy) {
	int col[10][10];
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			if ((posx / (1 << i)) % 2 == 1) col[i][j] = 0;
			else if ((posy / (1 << j)) % 2 == 1) col[i][j] = 0;
			else if (c[i][j] == '#') col[i][j] = 1;
			else col[i][j] = 2;
		}
	}

	int pats = 0;
	for (int i = 0; i < H; i++) {
		if ((posx / (1 << i)) % 2 == 1) continue;
		int c1 = 0, c2 = 0;
		for (int j = 0; j < W; j++) {
			if (col[i][j] == 1) c1++;
			if (col[i][j] == 2) c2++;
		}
		if (c1 * c2 == 0) pats++;
	}
	for (int i = 0; i < W; i++) {
		if ((posy / (1 << i)) % 2 == 1) continue;
		int c1 = 0, c2 = 0;
		for (int j = 0; j < H; j++) {
			if (col[j][i] == 1) c1++;
			if (col[j][i] == 2) c2++;
		}
		if (c1 * c2 == 0) pats++;
	}
	if (pats == 0) return true;
	return false;
}

int main() {
	// 入力
	init();
	cin >> H >> W;
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) cin >> c[i][j];
	}

	// 前処理
	for (int i = 0; i <= H; i++) {
		for (int j = 0; j <= W; j++) {
			solve(i, j, vector<int>{});
		}
	}
	dfs(0, 0);

	// 全探索
	long long Answer = 0;
	for (int i = 0; i < (1 << H); i++) {
		for (int j = 0; j < (1 << W); j++) {
			if (dfs(i, j) == false) continue;
			int f1 = bitcnt[i], f2 = bitcnt[j];
			if (f1 == H && f2 == W) continue;
			if (f1 == 0 && f2 == 0) Answer += 1LL;
			if (f1 == 0 && f2 >= 1) Answer += (1LL << f2);
			if (f1 >= 1 && f2 == 0) Answer += (1LL << f1);
			if (f1 >= 1 && f2 >= 1) Answer += dp3[f1][f2];
		}
	}
	Answer += dp0[H][W];
	cout << Answer % mod << endl;
	return 0;
}