#include <iostream>
#include <iomanip>
#include <cstdio>
#include <algorithm>
#include <numeric>
#include <random>
#include <vector>
#include <array>
#include <bitset>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>

using namespace std;
using ll = long long;
using ull = unsigned long long;
constexpr ll TEN(int n) { return (n==0) ? 1 : 10*TEN(n-1); }
int bsr(int x) { return 31 - __builtin_clz(x); }

template<class T>
T pow(T x, ll n, T r = 1) {
    while (n) {
        if (n & 1) r *= x;
        x *= x;
        n >>= 1;
    }
    return r;
}

template<uint MD>
struct ModInt {
    uint v;
    ModInt() : v{0} {}
    ModInt(ll v) : v{normS(v%MD+MD)} {}
    static uint normS(const uint &x) {return (x<MD)?x:x-MD;};
    static ModInt make(const uint &x) {ModInt m; m.v = x; return m;}
    ModInt operator+(const ModInt &r) const {return make(normS(v+r.v));}
    ModInt operator-(const ModInt &r) const {return make(normS(v+MD-r.v));}
    ModInt operator*(const ModInt &r) const {return make((ull)v*r.v%MD);}
    ModInt& operator+=(const ModInt &r) {return *this=*this+r;}
    ModInt& operator-=(const ModInt &r) {return *this=*this-r;}
    ModInt& operator*=(const ModInt &r) {return *this=*this*r;}
    static ModInt inv(const ModInt &x) {
        return pow(ModInt(x), MD-2);
    }
};
using Mint = ModInt<TEN(9)+7>;

// using B = vector<string>;
// set<B> s;
// void dfs(B b) {
//     if (s.count(b)) return;
//     s.insert(b);
//     cout << b[0] << endl << b[1] << endl;
//     swap(b[0][0], b[0][1]);
//     dfs(b);
//     swap(b[0][0], b[0][1]);
//     swap(b[0][0], b[1][0]);
//     dfs(b);
//     swap(b[0][0], b[1][0]);
//     swap(b[1][0], b[1][1]);
//     dfs(b);
//     swap(b[1][0], b[1][1]);
//     swap(b[0][1], b[1][1]);
//     dfs(b);
//     swap(b[0][1], b[1][1]);
// }

const int MN = 220;
using P = pair<int, int>;

Mint off = 1;

int co(vector<char> v) {
    sort(v.begin(), v.end());
/*    for (char c: v) {
        cout << c;
    } cout << endl;*/
    set<vector<char>> s;
    do {
        s.insert(v);
    } while (next_permutation(v.begin(), v.end()));
    return int(s.size());
}

bool coun(vector<char> v) {
    int u = co(v);
    if (u != 24) {
        off *= u;
        return false;
    }
    return true;
}

char g[MN][MN];
Mint d[MN][MN];

int main() {
    cout << setprecision(20);
    int h, w;
    cin >> h >> w;

    for (int y = 0; y < h; y++) {
        string s;
        cin >> s;
        for (int x = 0; x < w; x++) {
            g[y][x] = s[x];
        }
    }

    if (h % 2) {
        string s1, s2;
        for (int x = 0; x < w; x++) {
            s1 += g[h/2][x];
            s2 += g[h/2][w-1-x];
        }
        if (s1 != s2) off *= 2;
    }
    if (w % 2) {
        string s1, s2;
        for (int x = 0; x < h; x++) {
            s1 += g[x][w/2];
            s2 += g[h-1-x][w/2];
        }
        if (s1 != s2) off *= 2;
    }

    if (min(h, w) == 1) {
        cout << off.v << endl;
        return 0;
    }

    int buf = 0;
    vector<int> yv, xv;
    for (int a = 0; a < h; a++) {
        int b = h-1-a;
        if (a >= b) continue;
        for (int c = 0; c < w; c++) {
            int d = w-1-c;
            if (c >= d) continue;
            vector<char> v;
            v.push_back(g[a][c]);
            v.push_back(g[a][d]);
            v.push_back(g[b][c]);
            v.push_back(g[b][d]);
            bool u = coun(v);
            if (u) {
                yv.push_back(a);
                xv.push_back(c);
                off *= 12;
            }
        }
    }
    sort(yv.begin(), yv.end());
    yv.erase(unique(begin(yv), end(yv)), end(yv));
    sort(xv.begin(), xv.end());
    xv.erase(unique(begin(xv), end(xv)), end(xv));

    int co = yv.size()+xv.size();
    co--;
    if (co >= 0) {
        off *= pow(Mint(2), co);
    }
    cout << off.v << 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 <iomanip>
#include <cstdio>
#include <algorithm>
#include <numeric>
#include <random>
#include <vector>
#include <array>
#include <bitset>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>

using namespace std;
using ll = long long;
using ull = unsigned long long;
constexpr ll TEN(int n) { return (n==0) ? 1 : 10*TEN(n-1); }
int bsr(int x) { return 31 - __builtin_clz(x); }

template<class T>
T pow(T x, ll n, T r = 1) {
    while (n) {
        if (n & 1) r *= x;
        x *= x;
        n >>= 1;
    }
    return r;
}

template<uint MD>
struct ModInt {
    uint v;
    ModInt() : v{0} {}
    ModInt(ll v) : v{normS(v%MD+MD)} {}
    static uint normS(const uint &x) {return (x<MD)?x:x-MD;};
    static ModInt make(const uint &x) {ModInt m; m.v = x; return m;}
    ModInt operator+(const ModInt &r) const {return make(normS(v+r.v));}
    ModInt operator-(const ModInt &r) const {return make(normS(v+MD-r.v));}
    ModInt operator*(const ModInt &r) const {return make((ull)v*r.v%MD);}
    ModInt& operator+=(const ModInt &r) {return *this=*this+r;}
    ModInt& operator-=(const ModInt &r) {return *this=*this-r;}
    ModInt& operator*=(const ModInt &r) {return *this=*this*r;}
    static ModInt inv(const ModInt &x) {
        return pow(ModInt(x), MD-2);
    }
};
using Mint = ModInt<TEN(9)+7>;

// using B = vector<string>;
// set<B> s;
// void dfs(B b) {
//     if (s.count(b)) return;
//     s.insert(b);
//     cout << b[0] << endl << b[1] << endl;
//     swap(b[0][0], b[0][1]);
//     dfs(b);
//     swap(b[0][0], b[0][1]);
//     swap(b[0][0], b[1][0]);
//     dfs(b);
//     swap(b[0][0], b[1][0]);
//     swap(b[1][0], b[1][1]);
//     dfs(b);
//     swap(b[1][0], b[1][1]);
//     swap(b[0][1], b[1][1]);
//     dfs(b);
//     swap(b[0][1], b[1][1]);
// }

const int MN = 220;
using P = pair<int, int>;

Mint off = 1;

int co(vector<char> v) {
    sort(v.begin(), v.end());
/*    for (char c: v) {
        cout << c;
    } cout << endl;*/
    set<vector<char>> s;
    do {
        s.insert(v);
    } while (next_permutation(v.begin(), v.end()));
    return int(s.size());
}

bool coun(vector<char> v) {
    int u = co(v);
    if (u != 24) {
        off *= u;
        return false;
    }
    return true;
}

char g[MN][MN];
Mint d[MN][MN];

int main() {
    cout << setprecision(20);
    int h, w;
    cin >> h >> w;

    for (int y = 0; y < h; y++) {
        string s;
        cin >> s;
        for (int x = 0; x < w; x++) {
            g[y][x] = s[x];
        }
    }

    if (h % 2) {
        string s1, s2;
        for (int x = 0; x < w; x++) {
            s1 += g[h/2][x];
            s2 += g[h/2][w-1-x];
        }
        if (s1 != s2) off *= 2;
    }
    if (w % 2) {
        string s1, s2;
        for (int x = 0; x < h; x++) {
            s1 += g[x][w/2];
            s2 += g[h-1-x][w/2];
        }
        if (s1 != s2) off *= 2;
    }

    if (min(h, w) == 1) {
        cout << off.v << endl;
        return 0;
    }

    int buf = 0;
    vector<int> yv, xv;
    for (int a = 0; a < h; a++) {
        int b = h-1-a;
        if (a >= b) continue;
        for (int c = 0; c < w; c++) {
            int d = w-1-c;
            if (c >= d) continue;
            vector<char> v;
            v.push_back(g[a][c]);
            v.push_back(g[a][d]);
            v.push_back(g[b][c]);
            v.push_back(g[b][d]);
            bool u = coun(v);
            if (u) {
                yv.push_back(a);
                xv.push_back(c);
                off *= 12;
            }
        }
    }
    sort(yv.begin(), yv.end());
    yv.erase(unique(begin(yv), end(yv)), end(yv));
    sort(xv.begin(), xv.end());
    xv.erase(unique(begin(xv), end(xv)), end(xv));

    int co = yv.size()+xv.size();
    co--;
    if (co >= 0) {
        off *= pow(Mint(2), co);
    }
    cout << off.v << endl;
    return 0;
}

```