{"raw_statement":[{"iden":"problem statement","content":"There is an $N \\times M$ grid and a player standing on it.  \nLet $(i,j)$ denote the square at the $i$\\-th row from the top and $j$\\-th column from the left of this grid.  \nEach square of this grid is black or white, which is represented by $N$ strings $S_1,S_2,\\dots,S_N$ of length $M$ as follows:\n\n*   if the $j$\\-th character of $S_i$ is `.`, square $(i,j)$ is white;\n*   if the $j$\\-th character of $S_i$ is `#`, square $(i,j)$ is black.\n\nThe grid is said to be **beautiful** when the following condition is satisfied.\n\n*   For every pair of integers $(i,j)$ such that $1 \\le i \\le N, 1 \\le j \\le M$, if square $(i,j)$ is black, the square under $(i,j)$ and the square to the immediate lower right of $(i,j)$ are also black (if they exist).\n*   Formally, all of the following are satisfied.\n    *   If square $(i,j)$ is black and square $(i+1,j)$ exists, square $(i+1,j)$ is also black.\n    *   If square $(i,j)$ is black and square $(i+1,j+1)$ exists, square $(i+1,j+1)$ is also black.\n\nTakahashi can paint zero or more white squares black, and he will do so to make the grid beautiful.  \nFind the number of different beautiful grids he can make, modulo $998244353$.  \nTwo grids are considered different when there is a square that has different colors in those two grids."},{"iden":"constraints","content":"*   $1 \\le N,M \\le 2000$\n*   $S_i$ is a string of length $M$ consisting of `.` and `#`."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$ $M$\n$S_1$\n$S_2$\n$\\vdots$\n$S_N$"},{"iden":"sample input 1","content":"2 2\n.#\n.."},{"iden":"sample output 1","content":"3\n\nHe can make the following three different beautiful grids:\n\n.#  .#  ##\n.#  ##  ##"},{"iden":"sample input 2","content":"5 5\n....#\n...#.\n..#..\n.#.#.\n#...#"},{"iden":"sample output 2","content":"92"},{"iden":"sample input 3","content":"25 25\n.........................\n.........................\n.........................\n.........................\n.........................\n.........................\n.........................\n.........................\n.........................\n.........................\n.........................\n.........................\n.........................\n.........................\n.........................\n.........................\n.........................\n.........................\n.........................\n.........................\n.........................\n.........................\n.........................\n.........................\n........................."},{"iden":"sample output 3","content":"604936632\n\nFind the count modulo $998244353$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}