Taco Grid Paths

You are given a grid of R rows and C columns. Each cell in the grid is either . representing an open cell or # representing an obstacle. Starting from the top-left corner and moving only right or down, your task is to find the number of ways to reach the bottom-right corner without stepping into a cell with an obstacle. Since the number of ways can be very large, output the answer modulo \(998244353\).

Problem Details

• You can move only right or down.
• You cannot traverse cells that contain an obstacle (#).
• If the start or the destination cell is blocked, the answer is 0.

The answer should be computed modulo \(998244353\).

inputFormat

The first line of input contains two integers R and C, representing the number of rows and columns respectively.

Each of the next R lines contains a string of length C consisting of characters . and # representing the grid.

outputFormat

Output a single integer: the number of ways to reach the bottom-right corner from the top-left corner modulo \(998244353\).

3 3
...
.#.
...

2