#include using namespace std; constexpr int MOD = 1e9 + 7; using ll = long long; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int H, W; cin >> H >> W; vector> grid(H, vector(W)); for (int i = 0; i < H; ++i) for (int j = 0; j < W; ++j) cin >> grid[i][j]; if (grid[0][0] != grid[H - 1][W - 1]) { cout << "0\n"; return 0; } // State compression: (i,j,k,l) -> single integer key auto index = [=](int i, int j, int k, int l) { return ((i * W + j) * H + k) * W + l; }; unordered_map dp; dp[index(0, 0, H - 1, W - 1)] = 1; int total_steps = H + W - 2; // Expand DP: for each step towards the middle for (int dist = 0; dist < (total_steps + 1) / 2; ++dist) { unordered_map next_dp; for (auto &pr : dp) { ll key = pr.first, val = pr.second; int tmp = key; int l = tmp % W; tmp /= W; int k = tmp % H; tmp /= H; int j = tmp % W; tmp /= W; int i = tmp; // Try all (right,down) from (i,j) for (auto [ni, nj] : vector>{{i+1,j}, {i,j+1}}) { if (ni < 0 || ni >= H || nj < 0 || nj >= W) continue; // Try all (left,up) from (k,l) for (auto [nk, nl] : vector>{{k-1,l}, {k,l-1}}) { if (nk < 0 || nk >= H || nl < 0 || nl >= W) continue; if (grid[ni][nj] == grid[nk][nl]) { next_dp[index(ni, nj, nk, nl)] = (next_dp[index(ni, nj, nk, nl)] + val) % MOD; } } } } dp = move(next_dp); } ll ans = 0; // Even length path: middle is a pair if (total_steps % 2 == 1) { int mid = total_steps / 2; for (auto &pr : dp) { int tmp = pr.first; int l = tmp % W; tmp /= W; int k = tmp % H; tmp /= H; int j = tmp % W; tmp /= W; int i = tmp; // Only left-right pair at midpoint if ((i + j == mid) && (k + l == H + W - 2 - mid) && ((abs(i - k) + abs(j - l)) == 1)) { ans = (ans + pr.second) % MOD; } } } // Odd length path: middle is a cell else { int mid = total_steps / 2; for (auto &pr : dp) { int tmp = pr.first; int l = tmp % W; tmp /= W; int k = tmp % H; tmp /= H; int j = tmp % W; tmp /= W; int i = tmp; if ((i == k) && (j == l) && (i + j == mid)) { ans = (ans + pr.second) % MOD; } } } cout << ans << '\n'; }