#include <bits/stdc++.h>
using namespace std;

const int N = 500;
const int Mod = 1e9 + 7;
int n, m, f[N], used[N]; char s[N][N]; vector <int> g[N];

inline int dec(int x) {return x < 0 ? x + Mod : x;}
inline int inc(int x) {return x >= Mod ? x - Mod : x;}

template <class T> inline void in(T &x) {
	x = 0; int f = 1; char ch = getchar();
	for (; ch<'0' || ch>'9';) {if (ch=='-') f=-1; ch = getchar();}
	for (; ch>='0' && ch<='9';) x = x*10 + ch-'0', ch = getchar();
	x *= f;
}

inline int Count(string p) {
	sort(p.begin(), p.end());
	int n = p.size(), res = f[(int)p.size()];
	for (int l = 0, r; l < n; l = r) {
		r = l;
		for (; r < n && p[r] == p[l];) ++r;
		res /= f[r - l];
	}
	return res;
}

inline void dfs(int u) {
	used[u] = 1;
	for (auto v : g[u])
		if (!used[v]) dfs(v);
}

int main() {
	in(n), in(m), f[0] = 1;
	for (int i = 1; i < 5; ++i) f[i] = f[i - 1] * i;
	for (int i = 0; i < n; ++i) scanf("%s", s[i]);

	int ans = 1;
	for (int i = 0; i < n / 2; ++i)
		for (int j = 0; j < m / 2; ++j) {
			string p = "";
			p += s[i][j];
			p += s[n - i - 1][j];
			p += s[i][m - j - 1];
			p += s[n - i - 1][m - j - 1];
			int z = Count(p);
			if (z == 24) {
				z = 12;
				g[i].push_back(n + j);
				g[n + j].push_back(i);
			}
			ans = 1LL * ans * z % Mod;
		}

	if (n & 1) {
		int ok = false;
		for (int i = 0; !ok && i < m / 2; ++i)
			if (s[n / 2][i] != s[n / 2][m - i - 1])
				ok = true, ans = inc(ans << 1);
	}
	if (m & 1) {
		int ok = false;
		for (int i = 0; !ok && i < n / 2; ++i)
			if (s[i][m / 2] != s[n - i - 1][m / 2])
				ok = true, ans = inc(ans << 1);
	}

	int res = n + m;
	for (int i = 0; i < n + m; ++i)
		if (!used[i]) -- res, dfs(i);
	for (int i = 0; i < res; ++i) ans = inc(ans << 1);
	printf("%d\n", ans);
	return 0;
}
### Prompt

Please provide a cpp coded solution to the problem described below:

Snuke has a grid with H rows and W columns. The square at the i-th row and j-th column contains a character S_{i,j}.

He can perform the following two kinds of operation on the grid:

* Row-reverse: Reverse the order of the squares in a selected row.
* Column-reverse: Reverse the order of the squares in a selected column.



For example, reversing the 2-nd row followed by reversing the 4-th column will result as follows:

<image>

By performing these operations any number of times in any order, how many placements of characters on the grid can be obtained?

Constraints

* 1≦H,W≦200
* S_{i,j} is a lowercase English letter (`a`-`z`).

Input

The input is given from Standard Input in the following format:


H W
S_{1,1}S_{1,2}...S_{1,W}
S_{2,1}S_{2,2}...S_{2,W}
:
S_{H,1}S_{H,2}...S_{H,W}


Output

Print the number of placements of characters on the grid that can be obtained, modulo 1000000007 (=10^9+7).

Examples

Input

2 2
cf
cf


Output

6


Input

1 12
codefestival


Output

2

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;

const int N = 500;
const int Mod = 1e9 + 7;
int n, m, f[N], used[N]; char s[N][N]; vector <int> g[N];

inline int dec(int x) {return x < 0 ? x + Mod : x;}
inline int inc(int x) {return x >= Mod ? x - Mod : x;}

template <class T> inline void in(T &x) {
	x = 0; int f = 1; char ch = getchar();
	for (; ch<'0' || ch>'9';) {if (ch=='-') f=-1; ch = getchar();}
	for (; ch>='0' && ch<='9';) x = x*10 + ch-'0', ch = getchar();
	x *= f;
}

inline int Count(string p) {
	sort(p.begin(), p.end());
	int n = p.size(), res = f[(int)p.size()];
	for (int l = 0, r; l < n; l = r) {
		r = l;
		for (; r < n && p[r] == p[l];) ++r;
		res /= f[r - l];
	}
	return res;
}

inline void dfs(int u) {
	used[u] = 1;
	for (auto v : g[u])
		if (!used[v]) dfs(v);
}

int main() {
	in(n), in(m), f[0] = 1;
	for (int i = 1; i < 5; ++i) f[i] = f[i - 1] * i;
	for (int i = 0; i < n; ++i) scanf("%s", s[i]);

	int ans = 1;
	for (int i = 0; i < n / 2; ++i)
		for (int j = 0; j < m / 2; ++j) {
			string p = "";
			p += s[i][j];
			p += s[n - i - 1][j];
			p += s[i][m - j - 1];
			p += s[n - i - 1][m - j - 1];
			int z = Count(p);
			if (z == 24) {
				z = 12;
				g[i].push_back(n + j);
				g[n + j].push_back(i);
			}
			ans = 1LL * ans * z % Mod;
		}

	if (n & 1) {
		int ok = false;
		for (int i = 0; !ok && i < m / 2; ++i)
			if (s[n / 2][i] != s[n / 2][m - i - 1])
				ok = true, ans = inc(ans << 1);
	}
	if (m & 1) {
		int ok = false;
		for (int i = 0; !ok && i < n / 2; ++i)
			if (s[i][m / 2] != s[n - i - 1][m / 2])
				ok = true, ans = inc(ans << 1);
	}

	int res = n + m;
	for (int i = 0; i < n + m; ++i)
		if (!used[i]) -- res, dfs(i);
	for (int i = 0; i < res; ++i) ans = inc(ans << 1);
	printf("%d\n", ans);
	return 0;
}
```