use std::collections::HashMap; const SDX: [isize; 2] = [-1, 0]; const SDY: [isize; 2] = [0, -1]; const GDX: [usize; 2] = [1, 0]; const GDY: [usize; 2] = [0, 1]; const MOD: usize = 1e9 as usize + 7; 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 temp = String::new(); std::io::stdin().read_line(&mut temp).ok(); temp.trim().chars().collect::>() }) .collect::>(); let mut mapping = HashMap::new(); for i in 0..h.min(w) { let j = (h+w)/2-1-i; let (starti, startj) = if h > w { (i, j) } else { (j, i) }; if (h + w) % 2 == 0 { mapping.insert((starti, startj, starti, startj), 1usize); } else { if starti+1 < h && grid[starti][startj] == grid[starti+1][startj] { *mapping.entry((starti, startj, starti+1, startj)).or_insert(0usize) += 1; } if startj+1 < w && grid[starti][startj] == grid[starti][startj+1] { *mapping.entry((starti, startj, starti, startj+1)).or_insert(0usize) += 1; } } } for _ in 0..(h+w)/2-1 { let mut next_mapping = HashMap::new(); for (&(sx, sy, gx, gy), &cnt) in mapping.iter() { for sdir in 0..2 { let snx = sx as isize + SDX[sdir]; let sny = sy as isize + SDY[sdir]; if snx < 0 || sny < 0 { continue; } let snx = snx as usize; let sny = sny as usize; for gdir in 0..2 { let gnx = gx + GDX[gdir]; let gny = gy + GDY[gdir]; if gnx == h || gny == w { continue; } if grid[snx][sny] == grid[gnx][gny] { *next_mapping.entry((snx, sny, gnx, gny)).or_insert(0usize) += cnt; *next_mapping.entry((snx, sny, gnx, gny)).or_insert(0usize) %= MOD; } } } } mapping = next_mapping; } println!("{}", mapping.get(&(0,0,h-1,w-1)).unwrap_or(&0usize)); }