{"raw_statement":[{"iden":"problem statement","content":"There is a grid with $H$ rows and $W$ columns where each square has one of the characters `X` and `Y` written on it. Let $(i, j)$ denote the square at the $i$\\-th row from the top and $j$\\-th column from the left. The characters on the grid are given as $H$ strings $S_1, S_2, \\dots, S_H$: the $j$\\-th character of $S_i$ is the character on square $(i, j)$.\nYou can set up fences across the grid between adjacent rows and columns. Fences may intersect. After setting up fences, a **block** is defined as the set of squares reachable from some square by repeatedly moving up, down, left, or right to the adjacent square without crossing fences. (See also Sample Output 1.)\nThere are $2^{H-1} \\times 2^{W-1}$ ways to set up fences. How many of them satisfy the following condition, modulo $998244353$?\n**Condition:** Each block has exactly two squares with `Y` written on it."},{"iden":"constraints","content":"*   $1 \\leq H \\leq 2000$\n*   $1 \\leq W \\leq 2000$\n*   $S_i \\ (1 \\leq i \\leq H)$ is a string of length $W$ consisting of `X` and `Y`."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$H$ $W$\n$S_1$\n$S_2$\n$\\vdots$\n$S_H$"},{"iden":"sample input 1","content":"2 3\nXYY\nYXY"},{"iden":"sample output 1","content":"2\n\nBelow are the eight ways to set up fences.\n\nX Y Y    X|Y Y    X Y|Y    X|Y|Y\n          |          |      | |\nY X Y    Y|X Y    Y X|Y    Y|X|Y\n\n\nX Y Y    X|Y Y    X Y|Y    X|Y|Y\n-----    -+---    ---+-    -+-+-\nY X Y    Y|X Y    Y X|Y    Y|X|Y\n\nFor instance, if a fence is set up between the $2$\\-nd and $3$\\-rd columns, the blocks are:\n\nXY\nYX\n\nY\nY\n\nEach of these blocks has exactly two `Y`s, so the condition is satisfied.\nIf a fence is set up between the $1$\\-st and $2$\\-nd rows and the $1$\\-st and $2$\\-nd columns, the blocks are:\n\nX\n\nYY\n\nY\n\nXY\n\nThese blocks, except the second, do not have exactly two `Y`s, so the condition is not satisfied."},{"iden":"sample input 2","content":"2 3\nXYX\nYYY"},{"iden":"sample output 2","content":"0\n\nThere is no way to set up fences to satisfy the condition."},{"iden":"sample input 3","content":"2 58\nYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXY\nYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXY"},{"iden":"sample output 3","content":"164036797\n\nPrint the number of ways modulo $998244353$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}