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ドル$.