use std::io::{self, BufRead}; const MOD: i64 = 998244353; fn main() { let stdin = io::stdin(); let mut lines = stdin.lock().lines(); let first_line = lines.next().unwrap().unwrap(); let mut hw = first_line.split_whitespace().map(|s| s.parse::<usize>().unwrap()); let h = hw.next().unwrap(); let w = hw.next().unwrap(); let mut map = Vec::new(); for _ in 0..h { let line = lines.next().unwrap().unwrap(); map.push(line.chars().collect::<Vec<_>>()); } if map[0][1] == '#' || map[1][0] == '#' { println!("0"); return; } let mut list = vec![Vec::new(); h + w]; for i in 0..h { for j in 0..w { list[i + j].push((i, j)); } } let mut dp = vec![vec![0; 2]; 2]; dp[0][1] = 1; for s in 1..h + w - 3 { let len_next = list[s + 1].len(); let mut ndp = vec![vec![0; len_next]; len_next]; for i in 0..dp.len() { for j in i + 1..dp.len() { if dp[i][j] == 0 { continue; } let (x, y) = list[s][i]; let (z, w) = list[s][j]; for &k in &[i as isize - 1, i as isize, i as isize + 1] { if k < 0 || k as usize >= list[s + 1].len() { continue; } let (x2, y2) = list[s + 1][k as usize]; if map[x2][y2] == '#' { continue; } if (x as isize - x2 as isize).abs() + (y as isize - y2 as isize).abs() != 1 { continue; } for &l in &[j as isize - 1, j as isize, j as isize + 1] { if l < 0 || l as usize >= list[s + 1].len() { continue; } let (z2, w2) = list[s + 1][l as usize]; if map[z2][w2] == '#' { continue; } if (z as isize - z2 as isize).abs() + (w as isize - w2 as isize).abs() != 1 { continue; } if k < l { ndp[k as usize][l as usize] = (ndp[k as usize][l as usize] + dp[i][j]) % MOD; } } } } } dp = ndp; } let result: i64 = dp[0].iter().sum::<i64>() % MOD; println!("{}", result); }