MOD = 10**9 + 7 H, W = map(int, input().split()) grid = [input().strip() for _ in range(H)] total_steps = H + W - 2 if total_steps % 2 != 0: print(0) exit() m = total_steps // 2 from collections import defaultdict def generate_a(k): a_list = [] for x in range(1, H + 1): y = k + 2 - x if 1 <= y <= W: a_list.append((x, y)) return a_list def generate_b(k): b_list = [] target_sum = H + W - k for x in range(1, H + 1): y = target_sum - x if 1 <= y <= W: b_list.append((x, y)) return b_list current_dp = defaultdict(int) # Initialize for k=0 a0 = (1, 1) b0 = (H, W) if grid[a0[0]-1][a0[1]-1] == grid[b0[0]-1][b0[1]-1]: current_dp[(a0, b0)] = 1 for k in range(m): next_dp = defaultdict(int) for (a, b), cnt in current_dp.items(): # Generate possible moves from a (right or down) a_moves = [] x, y = a if y + 1 <= W: a_moves.append((x, y + 1)) if x + 1 <= H: a_moves.append((x + 1, y)) # Generate possible moves from b (left or up) bx, by = b b_moves = [] if by - 1 >= 1: b_moves.append((bx, by - 1)) if bx - 1 >= 1: b_moves.append((bx - 1, by)) # Check all combinations for a_new in a_moves: for b_new in b_moves: if grid[a_new[0]-1][a_new[1]-1] == grid[b_new[0]-1][b_new[1]-1]: next_dp[(a_new, b_new)] = (next_dp[(a_new, b_new)] + cnt) % MOD current_dp = next_dp # Sum all pairs where a == b answer = 0 for (a, b), cnt in current_dp.items(): if a == b: answer = (answer + cnt) % MOD print(answer)