#include <iostream>
#include <algorithm>
#include <map>
#include <utility>
#include <vector>
#define llint long long
#define mod 1000000007

using namespace std;
typedef pair<llint, llint> P;

struct UnionFind{
	int size;
	vector<int> parent;
	
	UnionFind(){}
	UnionFind(int size){
		this->size = size;
		parent.resize(size+1);
		init();
	}
	void init(){
		for(int i = 0; i <= size; i++) parent[i] = i;
	}
	int root(int i){
		if(parent[i] == i) return i;
		return parent[i] = root(parent[i]);
	}
	bool same(int i, int j){
		return root(i) == root(j);
	}
	void unite(int i, int j){
		int root_i = root(i), root_j = root(j);
		if(root_i == root_j) return;
		parent[root_i] = root_j;
	}
};

llint h, w;
char c[205][205];
bool b[205][205];
map<char, llint> mp;
map<llint, P> mp2;
UnionFind uf(405);

const int FACT_MAX = 15;
llint fact[FACT_MAX], fact_inv[FACT_MAX];

llint modpow(llint a, llint n)
{
	if(n == 0) return 1;
	if(n % 2){
		return ((a%mod) * (modpow(a, n-1)%mod)) % mod;
	}
	else{
		return modpow((a*a)%mod, n/2) % mod;
	}
}

void make_fact()
{
	llint val = 1;
	fact[0] = 1;
	for(int i = 1; i < FACT_MAX; i++){
		val *= i;
		val %= mod;
		fact[i] = val;
	}
	fact_inv[FACT_MAX-1] = modpow(fact[FACT_MAX-1], mod-2);
	for(int i = FACT_MAX-2; i >= 0; i--){
		fact_inv[i] = fact_inv[i+1] * (i+1) % mod;
	}
}

int main(void)
{
	make_fact();
	
	cin >> h >> w;
	for(int y = 1; y <= h; y++){
		for(int x = 1; x <= w; x++){
			cin >> c[x][y];
		}
	}
	
	llint ans = 1;
	if(h % 2){
		string s, t;
		for(int i = 1; i <= w; i++) s += c[i][h/2+1];
		t = s;
		reverse(t.begin(), t.end());
		if(s != t) ans *= 2;
		
		for(int y = h/2+1; y < h; y++){
			for(int x = 1; x <= w; x++){
				c[x][y] = c[x][y+1];
			}
		}
		h--;
	}
	if(w % 2){
		string s, t;
		for(int i = 1; i <= h; i++) s += c[w/2+1][i];
		t = s;
		reverse(t.begin(), t.end());
		if(s != t) ans *= 2;
		
		for(int x = w/2+1; x < w; x++){
			for(int y = 1; y <= h; y++){
				c[x][y] = c[x+1][y];
			}
		}
		w--;
	}
	
	if(h >= 1 && w >= 1){
		for(int y = 1; y <= h/2; y++){
			for(int x = 1; x <= w/2; x++){
				mp.clear();
				mp[c[x][y]]++;
				mp[c[w+1-x][y]]++;
				mp[c[w+1-x][h+1-y]]++;
				mp[c[x][h+1-y]]++;
				llint mul = fact[4];
				for(auto it = mp.begin(); it != mp.end(); it++) mul /= fact[it->second];
				if(mp.size() == 4) mul /= 2, b[x][y] = true;
				ans *= mul, ans %= mod;
			}
		}
	}
	
	h /= 2, w /= 2;
	for(int y = 1; y <= h; y++){
		for(int x = 1; x <= w; x++){
			if(b[x][y]) uf.unite(x, w+y);
		}
	}
	for(int x = 1; x <= w; x++) mp2[uf.root(x)].first++;
	for(int y = 1; y <= h; y++) mp2[uf.root(y+w)].second++;
	
	llint cnt = 0;
	for(auto it = mp2.begin(); it != mp2.end(); it++){
		cnt += it->second.first + it->second.second - 1;
	}
	ans *= modpow(2, cnt), ans %= mod;
	
	cout << ans << endl;
	
	return 0;
}
### Prompt

Create a solution in cpp for the following problem:

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 <iostream>
#include <algorithm>
#include <map>
#include <utility>
#include <vector>
#define llint long long
#define mod 1000000007

using namespace std;
typedef pair<llint, llint> P;

struct UnionFind{
	int size;
	vector<int> parent;
	
	UnionFind(){}
	UnionFind(int size){
		this->size = size;
		parent.resize(size+1);
		init();
	}
	void init(){
		for(int i = 0; i <= size; i++) parent[i] = i;
	}
	int root(int i){
		if(parent[i] == i) return i;
		return parent[i] = root(parent[i]);
	}
	bool same(int i, int j){
		return root(i) == root(j);
	}
	void unite(int i, int j){
		int root_i = root(i), root_j = root(j);
		if(root_i == root_j) return;
		parent[root_i] = root_j;
	}
};

llint h, w;
char c[205][205];
bool b[205][205];
map<char, llint> mp;
map<llint, P> mp2;
UnionFind uf(405);

const int FACT_MAX = 15;
llint fact[FACT_MAX], fact_inv[FACT_MAX];

llint modpow(llint a, llint n)
{
	if(n == 0) return 1;
	if(n % 2){
		return ((a%mod) * (modpow(a, n-1)%mod)) % mod;
	}
	else{
		return modpow((a*a)%mod, n/2) % mod;
	}
}

void make_fact()
{
	llint val = 1;
	fact[0] = 1;
	for(int i = 1; i < FACT_MAX; i++){
		val *= i;
		val %= mod;
		fact[i] = val;
	}
	fact_inv[FACT_MAX-1] = modpow(fact[FACT_MAX-1], mod-2);
	for(int i = FACT_MAX-2; i >= 0; i--){
		fact_inv[i] = fact_inv[i+1] * (i+1) % mod;
	}
}

int main(void)
{
	make_fact();
	
	cin >> h >> w;
	for(int y = 1; y <= h; y++){
		for(int x = 1; x <= w; x++){
			cin >> c[x][y];
		}
	}
	
	llint ans = 1;
	if(h % 2){
		string s, t;
		for(int i = 1; i <= w; i++) s += c[i][h/2+1];
		t = s;
		reverse(t.begin(), t.end());
		if(s != t) ans *= 2;
		
		for(int y = h/2+1; y < h; y++){
			for(int x = 1; x <= w; x++){
				c[x][y] = c[x][y+1];
			}
		}
		h--;
	}
	if(w % 2){
		string s, t;
		for(int i = 1; i <= h; i++) s += c[w/2+1][i];
		t = s;
		reverse(t.begin(), t.end());
		if(s != t) ans *= 2;
		
		for(int x = w/2+1; x < w; x++){
			for(int y = 1; y <= h; y++){
				c[x][y] = c[x+1][y];
			}
		}
		w--;
	}
	
	if(h >= 1 && w >= 1){
		for(int y = 1; y <= h/2; y++){
			for(int x = 1; x <= w/2; x++){
				mp.clear();
				mp[c[x][y]]++;
				mp[c[w+1-x][y]]++;
				mp[c[w+1-x][h+1-y]]++;
				mp[c[x][h+1-y]]++;
				llint mul = fact[4];
				for(auto it = mp.begin(); it != mp.end(); it++) mul /= fact[it->second];
				if(mp.size() == 4) mul /= 2, b[x][y] = true;
				ans *= mul, ans %= mod;
			}
		}
	}
	
	h /= 2, w /= 2;
	for(int y = 1; y <= h; y++){
		for(int x = 1; x <= w; x++){
			if(b[x][y]) uf.unite(x, w+y);
		}
	}
	for(int x = 1; x <= w; x++) mp2[uf.root(x)].first++;
	for(int y = 1; y <= h; y++) mp2[uf.root(y+w)].second++;
	
	llint cnt = 0;
	for(auto it = mp2.begin(); it != mp2.end(); it++){
		cnt += it->second.first + it->second.second - 1;
	}
	ans *= modpow(2, cnt), ans %= mod;
	
	cout << ans << endl;
	
	return 0;
}
```