use std::collections::{HashMap, HashSet}; const MOD: usize = 1e9 as usize + 7; const SDX: [isize; 2] = [1, 0]; const SDY: [isize; 2] = [0, 1]; const EDX: [isize; 2] = [-1, 0]; const EDY: [isize; 2] = [0, -1]; fn main() { let mut hw = String::new(); std::io::stdin().read_line(&mut hw).ok(); let hw: Vec = hw.trim().split_whitespace().map(|s| s.parse().unwrap()).collect(); let h = hw[0]; let w = hw[1]; let grid = (0..h).map(|_| { let mut s = String::new(); std::io::stdin().read_line(&mut s).ok(); let s = s.trim(); s.chars().map(|c| c as usize - 'a' as usize).collect::>() }) .collect::>>(); if grid[0][0] != grid[h-1][w-1] { println!("0"); return; } let mut dp = HashMap::new(); if (h+w) % 2 == 0 { for i in 0..h.min(w) { let x = if h > w { (h+w)/2-1-i } else { i }; let y = if w >= h { (h+w)/2-1-i } else { i }; dp.insert((x, y, x, y), 1); } } else { for i in 0..h.min(w) { let x = if h > w { (h+w)/2-1-i } else { i }; let y = if w >= h { (h+w)/2-1-i } else { i }; for dir in 0..2 { let nx = x as isize + SDX[dir]; let ny = y as isize + SDY[dir]; if nx >= 0 && ny >= 0 && nx < h as isize && ny < w as isize { let nx = nx as usize; let ny = ny as usize; if grid[x][y] == grid[nx][ny] { *dp.entry((x, y, nx, ny)).or_insert(0usize) += 1; } } } } } for _ in 0..(h+w)/2-1 { let mut next_dp = HashMap::new(); for (&(sx, sy, gx, gy), &cnt) in dp.iter() { for sdir in 0..2 { let nsx = sx as isize + EDX[sdir]; let nsy = sy as isize + EDY[sdir]; if !(nsx >= 0 && nsy >= 0 && nsx < h as isize && nsy < w as isize) { continue; } let nsx = nsx as usize; let nsy = nsy as usize; for gdir in 0..2 { let ngx = gx as isize + SDX[gdir]; let ngy = gy as isize + SDY[gdir]; if !(ngx >= 0 && ngy >= 0 && ngx < h as isize && ngy < w as isize) { continue; } let ngx = ngx as usize; let ngy = ngy as usize; if grid[nsx][nsy] == grid[ngx][ngy] { *next_dp.entry((nsx, nsy, ngx, ngy)).or_insert(0usize) += cnt; *next_dp.entry((nsx, nsy, ngx, ngy)).or_insert(0usize) %= MOD; } } } } dp = next_dp; } println!("{}", dp.get(&(0, 0, h-1, w-1)).unwrap_or(&0usize)); }