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

const int N = 250;
const int mod = 1e9 + 7;

int n, m;
char a[N][N];
int res = 1;
int par[N];

int anc(int p) { return p == par[p] ? p : par[p] = anc(par[p]); }
void join(int p, int q) { par[anc(p)] = anc(q); }

bool is_palind(string &s) {
    for (int i = 0; i < s.size() / 2; ++i) {
        if (s[i] != s[s.size() - 1 - i]) return false;
    }
    return true;
}

void cut_row() {
    string s = "";
    int mid = n / 2;
    for (int i = 0; i < m; ++i) {
        s += a[mid][i];
    }
    if (!is_palind(s)) {
        res *= 2;
    }
    --n;
    for (int i = mid; i < n; ++i) {
        for (int j = 0; j < m; ++j) a[i][j] = a[i + 1][j];
    }
}

void cut_col() {
    string s = "";
    int mid = m / 2;
    for (int i = 0; i < n; ++i) {
        s += a[i][mid];
    }
    if (!is_palind(s)) {
        res *= 2;
    }
    --m;
    for (int i = mid; i < m; ++i) {
        for (int j = 0; j < n; ++j) a[j][i] = a[j][i + 1];
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> a[i][j];
        }
    }

    if (n & 1) {
        cut_row();
    }
    if (m & 1) {
        cut_col();
    }

    // solve
	for (int i = 0; i < n / 2 + m / 2; ++i) par[i] = i;

    for (int i = 0; i < n / 2; ++i) {
        for (int j = 0; j < m / 2; ++j) {
            vector<char> cur;
            cur.push_back(a[i][j]);
            cur.push_back(a[n - i - 1][j]);
            cur.push_back(a[i][m - j - 1]);
            cur.push_back(a[n - i - 1][m - j - 1]);

            sort(cur.begin(), cur.end());
            int cnt = 0;
            do {
                ++cnt;
            } while(next_permutation(cur.begin(), cur.end()));

			if (cnt == 24) {
				res = 12LL * res % mod;
				join(i, j + n / 2);
			} else {
				res = 1LL * res * cnt % mod;
			}
        }
    }

	int ncomp = 0;
	for (int i = 0; i < n / 2 + m / 2; ++i) {
		if (i == par[i]) {
			++ncomp;
		}
	}

	for (int i = 0; i < n / 2 + m / 2 - ncomp; ++i) {
		res = 2LL * res % mod;
	}

    cout << res << endl;
}
### 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 <bits/stdc++.h>
using namespace std;

const int N = 250;
const int mod = 1e9 + 7;

int n, m;
char a[N][N];
int res = 1;
int par[N];

int anc(int p) { return p == par[p] ? p : par[p] = anc(par[p]); }
void join(int p, int q) { par[anc(p)] = anc(q); }

bool is_palind(string &s) {
    for (int i = 0; i < s.size() / 2; ++i) {
        if (s[i] != s[s.size() - 1 - i]) return false;
    }
    return true;
}

void cut_row() {
    string s = "";
    int mid = n / 2;
    for (int i = 0; i < m; ++i) {
        s += a[mid][i];
    }
    if (!is_palind(s)) {
        res *= 2;
    }
    --n;
    for (int i = mid; i < n; ++i) {
        for (int j = 0; j < m; ++j) a[i][j] = a[i + 1][j];
    }
}

void cut_col() {
    string s = "";
    int mid = m / 2;
    for (int i = 0; i < n; ++i) {
        s += a[i][mid];
    }
    if (!is_palind(s)) {
        res *= 2;
    }
    --m;
    for (int i = mid; i < m; ++i) {
        for (int j = 0; j < n; ++j) a[j][i] = a[j][i + 1];
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> a[i][j];
        }
    }

    if (n & 1) {
        cut_row();
    }
    if (m & 1) {
        cut_col();
    }

    // solve
	for (int i = 0; i < n / 2 + m / 2; ++i) par[i] = i;

    for (int i = 0; i < n / 2; ++i) {
        for (int j = 0; j < m / 2; ++j) {
            vector<char> cur;
            cur.push_back(a[i][j]);
            cur.push_back(a[n - i - 1][j]);
            cur.push_back(a[i][m - j - 1]);
            cur.push_back(a[n - i - 1][m - j - 1]);

            sort(cur.begin(), cur.end());
            int cnt = 0;
            do {
                ++cnt;
            } while(next_permutation(cur.begin(), cur.end()));

			if (cnt == 24) {
				res = 12LL * res % mod;
				join(i, j + n / 2);
			} else {
				res = 1LL * res * cnt % mod;
			}
        }
    }

	int ncomp = 0;
	for (int i = 0; i < n / 2 + m / 2; ++i) {
		if (i == par[i]) {
			++ncomp;
		}
	}

	for (int i = 0; i < n / 2 + m / 2 - ncomp; ++i) {
		res = 2LL * res % mod;
	}

    cout << res << endl;
}
```