You have a grid board with $$$n$$$ rows and $$$m$$$ columns. Let $$$(i,j)$$$ denote the cell in the $$$i$$$-th row from the top and the $$$j$$$-th column from the left. Some of the cells on the board may contain obstacles, except for the four corners.
A white piece and a black piece are on the board. Initially, the white piece is placed in the top-left corner cell $$$(1,1)$$$, and the black piece is placed in the bottom-left corner cell $$$(n,1)$$$.
You move the two pieces alternately. You first move the white piece. In one move, you move the white piece to the adjacent cell to the right or below, and you move the black piece to the adjacent cell to the right or above. Two cells are considered adjacent if they share an edge. However, you cannot move a piece onto a cell containing an obstacle. Also, you cannot move a piece onto a cell occupied by the other piece.
You want to move the two pieces $$$n+m-2$$$ times each, so that the white piece reaches the bottom-right corner cell $$$(n,m)$$$ and the black piece reaches the top-right corner cell $$$(1,m)$$$. Find the number of the pairs of such moving paths modulo $$$998\,244\,353$$$.
 |
| Figure G.1: One way to move the pieces for the first test case of Sample Input 1 |
The input consists of one or more test cases. Each test case is given in the following format.
| $$$n$$$ $$$m$$$ |
| $$$s_{1,1}s_{1,2}\cdots s_{1,m}$$$ |
| $$$\vdots$$$ |
| $$$s_{n,1}s_{n,2}\cdots s_{n,m}$$$ |
The integers $$$n$$$ and $$$m$$$ denote the numbers of rows and columns of the grid, respectively ($$$2\leq n\leq 10^6, 2\leq m\leq 10^6, n\times m\leq 2\times 10^6$$$). Each of the following $$$n$$$ lines contains a string of length $$$m$$$ consisting of '#' and '.', representing whether or not an obstacle is there. If $$$s_{i,j}$$$ is '#', cell $$$(i,j)$$$ contains an obstacle, and if it is '.', the cell does not contain an obstacle. The characters $$$s_{1,1},s_{1,m},s_{n,1},$$$ and $$$s_{n,m}$$$ are always '.'.
The end of the input is indicated by a line containing two zeros. The number of test cases does not exceed $$$200$$$. The sum of $$$n\times m$$$ over all the test cases does not exceed $$$2\times 10^6$$$.
For each test case, output in a line the number of the pairs of the moving paths modulo $$$998\,244\,353$$$.
3 3 .#. ... ... 4 7 ....... ###.### ###.### ....... 2 2 .. .. 11 27 ........................... ........................... ........................... ...###...##...###....##.... ....#...#..#..#..#..#..#... ....#...#.....###...#...... ....#...#..#..#.....#..#... ...###...##...#......##.... ........................... ........................... ........................... 0 0
3 0 1 40019649
