import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.util.StringTokenizer; public class Main { // 998244353 での剰余演算を行う static final long MOD = 998244353L; public static void main(String[] args) throws IOException { // 入力の高速化 BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int height = Integer.parseInt(st.nextToken()); int width = Integer.parseInt(st.nextToken()); // グリッドの入力 char[][] grid = new char[height][width]; for (int i = 0; i < height; i++) { String line = br.readLine(); grid[i] = line.toCharArray(); } // 特殊ケース:高さまたは幅が2の場合は、全セルが通行可能なら答えは1、1つでも壁があれば0 if (height == 2 || width == 2) { long result = 1; for (int i = 0; i < height; i++) { for (int j = 0; j < width; j++) { if (grid[i][j] == '#') { result = 0; break; } } } System.out.println(result); return; } // 2×2の行列 mat の各成分を計算する long[][] mat = new long[2][2]; // mat[0][0] : 先頭行を削除し、各行の末尾を削除したグリッドの最短経路数 char[][] grid00 = subGrid(grid, true, false, false, true); long[][] dp00 = countLatticePath(grid00); mat[0][0] = dp00[grid00.length - 1][grid00[0].length - 1]; // mat[0][1] : 先頭行と末尾行を削除したグリッドの最短経路数 char[][] grid01 = subGrid(grid, true, true, false, false); long[][] dp01 = countLatticePath(grid01); mat[0][1] = dp01[grid01.length - 1][grid01[0].length - 1]; // mat[1][0] : 各行の先頭と末尾を削除したグリッドの最短経路数 char[][] grid10 = subGrid(grid, false, false, true, true); long[][] dp10 = countLatticePath(grid10); mat[1][0] = dp10[grid10.length - 1][grid10[0].length - 1]; // mat[1][1] : 各行の先頭を削除し、末尾行を削除したグリッドの最短経路数 char[][] grid11 = subGrid(grid, false, true, true, false); long[][] dp11 = countLatticePath(grid11); mat[1][1] = dp11[grid11.length - 1][grid11[0].length - 1]; // 最終結果の計算: mat[0][0] * mat[1][1] - mat[0][1] * mat[1][0] (mod MOD) long result = (mat[0][0] * mat[1][1] % MOD - mat[0][1] * mat[1][0] % MOD + MOD) % MOD; System.out.println(result); } /** * 格子状のグリッドにおいて、始点 (0,0) から各セルまでの最短経路数を動的計画法 (DP) で計算する * 通行不可のセルは '#' で表される * * @param grid 格子(2次元の文字配列) * @return 各セルまでの経路数を格納した 2 次元配列 */ static long[][] countLatticePath(char[][] grid) { int h = grid.length; int w = grid[0].length; long[][] dp = new long[h][w]; // 始点が壁でなければ 1 をセット dp[0][0] = (grid[0][0] == '#' ? 0 : 1); for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { // 壁の場合は経路数を計算しない if (grid[i][j] == '#') { continue; } if (i == 0 && j == 0) { continue; } long ways = 0; // 上から来る場合 if (i > 0) { ways = (ways + dp[i - 1][j]) % MOD; } // 左から来る場合 if (j > 0) { ways = (ways + dp[i][j - 1]) % MOD; } dp[i][j] = ways; } } return dp; } /** * グリッドの部分コピーを作成する * * @param grid 元のグリッド * @param removeFirstRow 最初の行を削除するか否か * @param removeLastRow 末尾の行を削除するか否か * @param removeFirstCol 各行の最初の要素を削除するか否か * @param removeLastCol 各行の末尾の要素を削除するか否か * @return 部分グリッド(新たな 2 次元文字配列) */ static char[][] subGrid(char[][] grid, boolean removeFirstRow, boolean removeLastRow, boolean removeFirstCol, boolean removeLastCol) { int originalRows = grid.length; int originalCols = grid[0].length; int startRow = removeFirstRow ? 1 : 0; int endRow = removeLastRow ? originalRows - 1 : originalRows; int startCol = removeFirstCol ? 1 : 0; int endCol = removeLastCol ? originalCols - 1 : originalCols; int newRows = endRow - startRow; int newCols = endCol - startCol; char[][] sub = new char[newRows][newCols]; for (int i = 0; i < newRows; i++) { for (int j = 0; j < newCols; j++) { sub[i][j] = grid[startRow + i][startCol + j]; } } return sub; } }