28167번 - Big Picture 다국어

Grammy has a big picture with $n+1$ rows and $m+1$ columns. Rows are numbered from $1$ to $n+1$ and columns are numbered from $1$ to $m+1$.

Grammy decides to color this picture in a special way. For the $i$-th row, Grammy will color the leftmost $j$ ($1\leq j\leq m$) cells black with probability $p_{i,j}$. For the $j$-th column, Grammy will color the topmost $i$ ($1\leq i\leq n$) cells black with probability $q_{i,j}$. Operations are independent, and a cell could be colored more than once.

Let us define the beauty value as the number of maximal orthogonally connected regions of the same color. Before Grammy finishes her coloring, she wants to know the expected number of regions on the picture. Please calculate the expected beauty value of the picture for her.

Two cells $x$ and $y$ are in the same orthogonally connected region if and only if they satisfy the following constraints:

• They have the same color.
• $x$ shares an edge with $y$ or $x$ shares an edge with some cell $z$ while $y$ and $z$ are in the same orthogonally connected region.

The first line contains two integers $n$ and $m$ ($1 \leq n,m \leq 1000$), denoting the size of the picture.

Each of the next $n$ lines contains $m$ integers $p_{i,j}$, denoting the probability of painting the leftmost $j$ cells of the $i$-th row black, modulo $998\,244\,353$. It is guaranteed that the sum of the probabilities in each row is $1$.

Each of the next $n$ lines contains $m$ integers $q_{i,j}$, denoting the probability of painting the topmost $i$ cells of the $j$-th column black, modulo $998\,244\,353$. It is guaranteed that the sum of the probabilities in each column is $1$.

Output a single integer, denoting the expected beauty value of the picture, modulo $998\,244\,353$.

It can be shown that the answer can be expressed as an irreducible fraction $\frac{x}{y}$, where $x$ and $y$ are integers and $y \not \equiv 0 \pmod {998\,244\,353}$. Output the integer equal to $x\cdot y^{-1}\pmod {998\,244\,353}$. In other words, output such an integer $a$ that $0\leq a < 998\,244\,353$ and $a\cdot y\equiv x\pmod {998\,244\,353}$.

There is only one possible picture in the first example, which is shown as follows. There are $3$ maximal orthogonally connected regions in the picture, so the beauty value of the picture is $3$.